题目描述
给你一个下标从 0 开始的整数数组 nums
。nums
的一个子数组如果满足以下条件,那么它是 不间断 的:
i,i + 1 ,...,j
表示子数组中的下标。对于所有满足i <= i_1, i_2 <= j
的下标对,都有0 <= |nums[i_1] - nums[i_2]| <= 2
。
请你返回 不间断 子数组的总数目。
子数组是一个数组中一段连续 非空 的元素序列。
样例
输入:nums = [5,4,2,4]
输出:8
解释:
大小为 1 的不间断子数组:[5], [4], [2], [4]。
大小为 2 的不间断子数组:[5,4], [4,2], [2,4]。
大小为 3 的不间断子数组:[4,2,4]。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8。
除了这些以外,没有别的不间断子数组。
输入:nums = [1,2,3]
输出:6
解释:
大小为 1 的不间断子数组:[1], [2], [3]。
大小为 2 的不间断子数组:[1,2], [2,3]。
大小为 3 的不间断子数组:[1,2,3]。
不间断子数组的总数目为 3 + 2 + 1 = 6。
限制
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
算法1
(双指针,多重有序集合) $O(n \log n)$
- 定义双指针 $i$ 和 $j$,对于每个结尾位置 $i$,都寻找尽可能小的 $j$,满足子数组 $[j, i], [j + 1, i], \dots [i, i]$ 都是不间断子数组。显然 $j$ 是随着 $i$ 增大而不减的。
- 使用多重集合记录区间内每个数字出现的次数。每次移动 $i$ 都将当前的数字加入多重集合,如果当前区间 $[j, i]$ 中最大和最小的数字相差超过了 $2$,则移动 $j$,并从多重集合中去掉对应的数字。
时间复杂度
- 每个位置最多被遍历两次,且最多进出集合一次。单次操作有序集合的时间复杂度为 $O(\log n)$,故时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储多重集合。
C++ 代码
#define LL long long
class Solution {
public:
LL continuousSubarrays(vector<int>& nums) {
const int n = nums.size();
LL ans = 0;
multiset<int> s;
for (int i = 0, j = 0; i < n; i++) {
s.insert(nums[i]);
while (*s.rbegin() - *s.begin() > 2) {
s.erase(s.find(nums[j]));
++j;
}
ans += i - j + 1;
}
return ans;
}
};
算法2
(双指针,单调队列) $O(n)$
- 延续算法 1 的思路,改用两个单调队列分别维护当前区间的最小值和最大值,两个队头分别记录的是区间 $[j, i]$ 的最小值和最大值。
- 每次移动 $i$,将当前值分别和两个队列的队尾进行比较,如果不满足单调性则出队,然后当前值进入队尾。
- 接下来判定当前区间是否满足最大值减去最小值小于等于 $2$,如果不满足,则移动 $j$,然后分别让两个队列的队头根据 $j$ 出队。
时间复杂度
- 每个位置最多被遍历两次,且最多进出集合一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储多重集合。
C++ 代码
#define LL long long
class Solution {
public:
LL continuousSubarrays(vector<int>& nums) {
const int n = nums.size();
deque<int> mi, ma;
LL ans = 0;
for (int i = 0, j = 0; i < n; i++) {
while (!mi.empty() && nums[mi.back()] >= nums[i]) mi.pop_back();
while (!ma.empty() && nums[ma.back()] <= nums[i]) ma.pop_back();
mi.push_back(i);
ma.push_back(i);
while (!mi.empty() && !ma.empty() &&
nums[ma.front()] - nums[mi.front()] > 2
) {
++j;
while (!mi.empty() && mi.front() < j) mi.pop_front();
while (!ma.empty() && ma.front() < j) ma.pop_front();
}
ans += i - j + 1;
}
return ans;
}
};