首先,我们考虑暴力的解法要怎么做?枚举每个子数组的起点,然后从这个起点向后遍历,每次把一个数插入一个有序的序列当中,再遍历一下这个有序序列看看有多少个不平衡数字,再累加起来得到答案。
这样的话,时间复杂度大约是$O(n^3)$或者$O(n^3logn)$, 具体就不考虑了, 反正是TLE的
然后我们考虑如何去优化这个过程? 我们注意到每一次都要遍历这个有序序列存在着很多的重复计算, 我们尝试维护这个不平衡数字的个数和, 来节省每一次遍历的过程, 这样可以把时间复杂度降到$O(n^2)$或者$O(n^2logn)$, 就可以过了
那这个过程是这样:
- 枚举每个子数组的起始位置, 从起始位置逐个向后遍历(逐个元素添加)
- 如果这个元素是原来有序序列有的元素, 那么他不会产生不平衡数字, 直接continue
- 当这个元素是整个有序序列的第一个元素, 即原序列为空, 新加入第一个元素, 是不会产生不平衡数字的(因为就一个元素, 甚至都不成对)
- 当这个元素不是第一个元素, 即原序列中有数字
- 如果比原序列的最大的元素还要大, 那么只可能和原来最大的元素产生不平衡数字, 和原序列的其他的元素不会产生, 而前者是否产生, 还要看差值是否满足
>1
的这个条件 - 如果比原序列的最小的元素还要小, 那么只可能和原来最小的元素产生不平衡数字, 和原序列的其他的元素不会产生, 而前者是否产生, 还要看差值是否满足
>1
的这个条件 - 如果都不是以上两种情况, 那么说明新加入的数字会至多产生2个不平衡数字, 是否产生和加入前最临近的比新加入元素大或者小的元素有关, 具体影响因素有: 原来这两个元素的差值? 新元素和比它大的最临近元素的关系? 新元素和比它小的最临近元素的关系? 根据影响因素, 我们维护的不平衡元素个数和可能增加或者减少或者不变, 分情况讨论;
- 举个例子来说, 如果原来序列有$4$和$6$, 他们之间本来会产生一个不平衡数字, 但是新加进来一个$5$, 原来那个不平衡数字就没有了, 会造成不平衡数字的减少;
- 再比如, 原来是有$4$和$7$, 他们之间本来会产生一个不平衡数字, 但是加进来一个$5$, 4和7之间的会消失, 但是$5$和$7$之间会产生不平衡数字, 所以个数和不变;
- 再比如原来是$5$和$9$, 现在加入一个$7$, $5$和$9$原本是有1个不平衡数字的, 现在它们之间没有了, 取而代之$5$和$7$, $7$和$9$ 之间都会产生1个不平衡数字, 总体个数和增加
- 如果比原序列的最大的元素还要大, 那么只可能和原来最大的元素产生不平衡数字, 和原序列的其他的元素不会产生, 而前者是否产生, 还要看差值是否满足
- 这个有序序列可以使用 并查集/平衡树来维护, 由于元素的值的范围较小, 我是使用的数组, 可以降低一点时间复杂度
时间复杂度 $O(n^2)$
class Solution {
public:
int sumImbalanceNumbers(vector<int>& nums) {
int res = 0;
int n = nums.size();
bool st[n + 2];
for (int i = 0; i < n; i ++) {
int sum = 0, sz = 0, mx = -1, mn = 1010;
// sz 记录不同的数字有几个
memset(st, 0, sizeof st);
for (int j = i; j < n; j ++) {
if (st[nums[j]]) {
res += sum;
continue;
}
st[nums[j]] = true;
if (sz == 0) {
mx = max(mx, nums[j]);
mn = min(mn, nums[j]);
}
else if (nums[j] > mx) {
sum += (nums[j] - mx > 1);
mx = nums[j];
}
else if (nums[j] < mn) {
sum += (mn - nums[j] > 1);
mn = nums[j];
}
else {
if (st[nums[j] + 1] and st[nums[j] - 1]) sum -= 1;
else if (!st[nums[j] + 1] and !st[nums[j] - 1]) sum += 1;
}
res += sum;
sz += 1;
}
}
return res;
}
};