C++单调向量算法应用：所有子数组中不平衡数字之和-摩杜云开发者社区

涉及知识点

单调向量

题目

一个长度为 n 下标从 0 开始的整数数组 arr 的不平衡数字定义为，在 sarr = sorted(arr) 数组中，满足以下条件的下标数目：
0 <= i < n - 1 ，和
sarr[i+1] - sarr[i] > 1
这里，sorted(arr) 表示将数组 arr 排序后得到的数组。
给你一个下标从 0 开始的整数数组 nums ，请你返回它所有子数组的不平衡数字之和。
子数组指的是一个数组中连续一段非空的元素序列。
示例 1：
输入：nums = [2,3,1,4]
输出：3
解释：总共有 3 个子数组有非 0 不平衡数字：

子数组 [3, 1] ，不平衡数字为 1 。
子数组 [3, 1, 4] ，不平衡数字为 1 。
子数组 [1, 4] ，不平衡数字为 1 。
其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 3 。
示例 2：
输入：nums = [1,3,3,3,5]
输出：8
解释：总共有 7 个子数组有非 0 不平衡数字：
子数组 [1, 3] ，不平衡数字为 1 。
子数组 [1, 3, 3] ，不平衡数字为 1 。
子数组 [1, 3, 3, 3] ，不平衡数字为 1 。
子数组 [1, 3, 3, 3, 5] ，不平衡数字为 2 。
子数组 [3, 3, 3, 5] ，不平衡数字为 1 。
子数组 [3, 3, 5] ，不平衡数字为 1 。
子数组 [3, 5] ，不平衡数字为 1 。
其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 8 。
参数范围：
1 <= nums.length <= 1000
1 <= nums[i] <= nums.length

分析

时间复杂度

O(n*logn),共五步，四步是是O(n)，一步是O(nlogn)，故总时间复杂度是O(nlogn)。

排在首位

左边没有数小于等于nums[i]，右边没有数据小于nums[i]。

原理

排序时，相同的数字相同顺序不变。依次枚举nums个元素，再计算所有子数组的不平衡数之和。如果左边有数等于nums[i]或nums[i]-1，则nums[i]一定不是不平衡数字。处理nums[i]时，包括nums[i]的子数组[l,r]，l其取值范围为(-1,i]，r取值范围为[i,m_c)。令l1是nums[l1]nums[i]或nums[l1]+1nums[i],l1取值范围为(-1,i)如果有多个l1，取最大值。令r1取值范围为(i,m_c),令nums[r1]==nums[i]-1，如果有多个r1，取最小值。如果l1不存在，取-1；如果r1不存在取m_c。如果l取[0,il]或r取[r1,m_c)，则nums[i]一定不是平衡数。


条件一	取[0,il]或r取[r1,m_c)
条件二	排在首位


情况一	条件一成立	条件二一定不成立	一定不是不平衡数
情况二	条件一不成立	条件二成立	一定不是不平衡数
情况二	条件一不成立	条件二不成立	是不平衡数

由于条件一和条件二不可能同时成立，所以情况二，可以简化为：条件二成立。

变量解释


num1	情况二和情况三
num2	情况二

单调向量

如果l11 < l12，且nums[l11] >= nums[l12],则l11被淘汰。这意味者：qLeft是单调递增，方便使用二分查找，

步骤

一，计算l1。
二，计算r1。
三，计算l2。
四，计算r2。
五，枚举nums[i]的不平衡数。

代码

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;res = slu.sumImbalanceNumbers(nums);
Assert(3 ,res);




//CConsole::Out(res);}

2023年8月旧代码一

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;
 };

2023年8月旧代码二

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;
 };

充满正能量得对大家说
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境：

VS2022 C++17

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

涉及知识点

题目

分析

时间复杂度

排在首位

原理

变量解释

单调向量

步骤

代码

核心代码

测试

2023年8月旧代码一

2023年8月旧代码二

相关下载

测试环境