C++ monotonic vector algorithm application: sum of unbalanced numbers in all subarrays

Involving knowledge points

monotonic vector

Title

The unbalanced number of an integer array arr of length n with indexes starting from 0 is defined as the number of indexes in the array sarr = sorted(arr) that satisfy the following conditions:
0 <= i < n - 1 , and
sarr[i + 1] – sarr[i] > 1
Here, sorted(arr) represents the array obtained by sorting the array arr.
Given an integer array nums whose index starts from 0, please return the sum of the unbalanced numbers of all its subarrays.
A subarray refers to a continuous non-empty sequence of elements in an array.
Example 1:
Input: nums = [2,3,1,4]
Output: 3
Explanation: There are a total of 3 subarrays with non-zero unbalanced numbers:

  • Subarray [3, 1] , unbalanced number is 1 .
  • Subarray [3, 1, 4] , unbalanced number is 1 .
  • Subarray [1, 4] , unbalanced number is 1 .
    The imbalance numbers of all other subarrays are 0 , so the sum of the imbalance numbers of all subarrays is 3 .
    Example 2:
    Input: nums = [1,3,3,3,5]
    Output: 8
    Explanation: There are a total of 7 subarrays with non-zero unbalanced numbers:
  • Subarray [1, 3] , unbalanced number is 1 .
  • Subarray [1, 3, 3] , unbalanced number is 1 .
  • Subarray [1, 3, 3, 3] , unbalanced number is 1 .
  • Subarray [1, 3, 3, 3, 5] with unbalanced number 2 .
  • Subarray [3, 3, 3, 5] , unbalanced number is 1 .
  • Subarray [3, 3, 5] , unbalanced number is 1 .
  • Subarray [3, 5] , unbalanced number is 1 .
    The unbalanced numbers of all other subarrays are 0 , so the sum of the unbalanced numbers of all subarrays is 8 .
    Parameter range:
    1 <= nums.length <= 1000
    1 <= nums[i] <= nums.length

Analysis

Time complexity

O(n*logn), a total of five steps, four steps is O(n), one step is O(nlogn), so the total time complexity is O(nlogn).

Ranked first

There is no number on the left that is less than or equal to nums[i], and there is no data on the right that is less than nums[i].

Principle

When sorting, the same numbers remain in the same order. Enumerate nums elements in sequence, and then calculate the sum of the unbalanced numbers of all subarrays. If there is a number on the left equal to nums[i] or nums[i]-1, then nums[i] must not be an unbalanced number. When processing nums[i], the subarray [l,r] of nums[i] is included. The value range of l is (-1,i], and the value range of r is [i,m_c). Let l1 be nums[l1]nums[i] or nums[l1] + 1nums[i]. The value range of l1 is (-1,i). If there are multiple l1s, take the maximum value. . Let the value range of r1 be (i,m_c), let nums[r1]==nums[i]-1, if there are multiple r1, take the minimum value. If l1 does not exist, take -1; if r1 does not exist, take m_c. If l takes [0,il] or r takes [r1,m_c), then nums[i] must not be a balanced number.
Condition 1 Take [0,il] or r takes [r1,m_c)
Condition 2 Ranked first
Case 1 Condition 1 is true Condition 2 must not be true It must not be an unbalanced number
Case 2 Condition 1 is not true Condition 2 is true It must not be an unbalanced number
Case 2 Condition 1 is not true Condition 2 is not true YesUnbalanced number

Since condition 1 and condition 2 cannot be true at the same time, situation 2 can be simplified as: condition 2 is true.

Variable explanation
num1 Case 2 and case three
num2 case two

Monotone vector

If l11 < l12, and nums[l11] >= nums[l12], then l11 is eliminated. This means: qLeft is monotonically increasing, which is convenient for binary search.

Steps

1. Calculate l1.
Second, calculate r1.
Third, calculate l2.
Fourth, calculate r2.
5. Enumerate the unbalanced number of nums[i].

Code

class Solution {
public:
int sumImbalanceNumbers(vector & amp; nums) {
m_c = nums.size();
const int iMaxValue = *std::max_element(nums.begin(), nums.end());
vector vLeftRange(m_c),vRightRange(m_c);
{
vector vLeft(iMaxValue + 1, -1);
for (int i = 0; i < m_c; i + + )
{
vLeftRange[i] = max(vLeft[nums[i]], vLeft[nums[i] – 1]);
vLeft[nums[i]] = i;
}
}
{
vector vRight(iMaxValue + 1, nums.size());
for (int i =m_c-1; i >= 0; i–)
{
vRightRange[i] = vRight[nums[i]-1];
vRight[nums[i]] = i;
}
}
vector vLeftRange2(m_c), vRightRange2(m_c);
{
vector> qLeft;
for (int i = 0; i < m_c; i + + )
{
auto it1 = std::upper_bound(qLeft.begin(), qLeft.end(), std::make_pair(nums[i] + 1, -1));
int left = (qLeft.begin() == it1) ? -1 : std::prev(it1)->second;
vLeftRange2[i] = left;
while (qLeft.size() & amp; & amp; (qLeft.back().first >= nums[i]))
{
qLeft.pop_back();
}
qLeft.emplace_back(nums[i], i);
}
}
{
vector> qRight;
for (int i = m_c – 1; i >= 0; i–)
{
auto it2 = std::upper_bound(qRight.begin(), qRight.end(), std::make_pair(nums[i], -1));
auto right = (qRight.begin() == it2) ? m_c : std::prev(it2)->second;
vRightRange2[i] = right;
while (qRight.size() & amp; & amp; (qRight.back().first >= nums[i]))
{
qRight.pop_back();
}
qRight.emplace_back(nums[i], i);
}
}
int iRet = 0;
for (int i = 0; i < m_c; i + + )
{
int num1 = (i – vLeftRange[i]) * (vRightRange[i] – i);//The left side does not include nums[i] and nums[i]-1, and the right side does not include the number of nums[i]
int num2 = (i – vLeftRange2[i]) * (vRightRange2[i] – i);//Everything on the left is larger than him, and the right is greater than or equal to it, that is, ranked to the far left
iRet + = num1 – num2;
}
return iRet;
}
int m_c;
};

Core code

Test

template
void Assert(const vector & amp; v1, const vector & amp; v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i + + )
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T & t1, const T & t2)
{
assert(t1 == t2);
}
int main()
{
Solution slug;
vector nums = {2,3,1,3};
int res;

res = slu.sumImbalanceNumbers(nums);
Assert(3,res);




//CConsole::Out(res);

}

Old code 1 in August 2023

class Solution {
public:
int sumImbalanceNumbers(vector & amp; nums) {
m_c = nums.size();
int iRet = 0;
for (int i = 0; i < m_c; i + + )
{
int iMin = nums[i], iMax = nums[i];
int iBalanceNum = 0;
std::unordered_set mVis;
mVis.emplace(nums[i]);
for (int j = i + 1; j < m_c; j + + )
{
const int & n = nums[j];
if (mVis.count(n))
{
iRet + = iBalanceNum;
continue;
}
if (n < iMin)
{
if (!mVis.count(n + 1))
{
iBalanceNum + + ;
}
iMin = n;
}
else if (n > iMax)
{
if (!mVis.count(n – 1))
{
iBalanceNum + + ;
}
iMax = n;
}
else
{
if (mVis.count(n – 1) & amp; & amp; mVis.count(n + 1))
{
iBalanceNum–;
}
if (mVis.count(n – 1) || mVis.count(n + 1))
{
}
else
{
iBalanceNum + + ;
}
}
iRet + = iBalanceNum;
mVis.emplace(n);
}
}
return iRet;
}
int m_c;
};

Old code two in August 2023

class Solution {
public:
int sumImbalanceNumbers(vector & amp; nums) {
m_c = nums.size();
int mVis[1001] = { 0 };
int iRet = 0;
for (int i = 0; i < m_c; i + + )
{
int iMin = nums[i], iMax = nums[i];
int iBalanceNum = 0;
memset(mVis, 0, sizeof(mVis));
mVis[nums[i]]= true;
for (int j = i + 1; j < m_c; j + + )
{
const int & n = nums[j];
if (mVis[n])
{
iRet + = iBalanceNum;
continue;
}
if (n < iMin)
{
if (!mVis[n + 1])
{
iBalanceNum + + ;
}
iMin = n;
}
else if (n > iMax)
{
if (!mVis[n – 1])
{
iBalanceNum + + ;
}
iMax = n;
}
else
{
if (mVis[n – 1] & amp; & amp; mVis[n + 1])
{
iBalanceNum–;
}
if (mVis[n – 1] || mVis[n + 1])
{
}
else
{
iBalanceNum + + ;
}
}
iRet + = iBalanceNum;
mVis[n]=true;
}
}
return iRet;
}
int m_c;
};

Extended reading

Video course

Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771

how fast do you want

A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176

Related downloads

If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653

I am full of positive energy and say it to everyone
It is a good wish to be happy when you hear the flaws. Discover problems early, correct them early, and save your boss money.
The origin of the Mohist name: everything is recorded in Mohism.
If the program is a one-stop process, then the algorithm is its key point

Test environment

Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:

VS2022 C++ 17