C++单调向量算法应用：所有子数组中不平衡数字之和

class Solution {
public:
int sumImbalanceNumbers(vector& 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<pair<int, int>> 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() && (qLeft.back().first >= nums[i]))
{
qLeft.pop_back();
}
qLeft.emplace_back(nums[i], i);
}
}
{
vector<pair<int, int>> 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() && (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);//左边不包括nums[i]和nums[i]-1，右边不包括nums[i]的数量
int num2 = (i - vLeftRange2[i]) * (vRightRange2[i] - i);//左边全部都比他大，右边大于等于，也就是排到最左边
iRet += num1 - num2;
}
return iRet;
}
int m_c;
};

template
void Assert(const vector& v1, const vector& 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 slu;
vector nums = {2,3,1,3 };
int res;

class Solution {
public:
int sumImbalanceNumbers(vector& 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)&& 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;
};

class Solution {
public:
int sumImbalanceNumbers(vector& 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] && mVis[n + 1])
{
iBalanceNum–;
}
if (mVis[n - 1] || mVis[n + 1])
{
}
else
{
iBalanceNum++;
}
}
iRet += iBalanceNum;
mVis[n]=true;
}
}
return iRet;
}
int m_c;
};