leet2762.continuous-subarrays

2762. 不间断子数组

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

• i，i + 1 ，…，j  表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。

请你返回 不间断 子数组的总数目。

子数组是一个数组中一段连续 非空 的元素序列。

示例 1：

输入： 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 。 除了这些以外，没有别的不间断子数组。

示例 2：

输入： 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

---

思路

参考leet1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit or 灵神题解

Code

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
	    const int n = nums.size();
	    long long ans = 0;
	    deque<int> maxq, minq;
        int l = 0, r = 0;
        for (; r < n; r++) {
	        while (!maxq.empty() && nums[r] > nums[maxq.back()])
		        maxq.pop_back();
		    maxq.push_back(r);
		    
		    while (!minq.empty() && nums[r] < nums[minq.back()])
			    minq.pop_back();
			minq.push_back(r);
			
			while (nums[maxq.front()] - nums[minq.front()] > 2) {
				l++;
				if (l > maxq.front()) maxq.pop_front();
				if (l > minq.front()) minq.pop_front();
			}
			
			// 每次确定好最大窗口[l,r]，固定r，共有
			// [l, r], [l+1, r], ..., [r, r] = [r]
			// r - l + 1 个子区间满足要求，
			// 下一次迭代r+1，继续这样统计，所以r遍历完之后，就得到所有满足条件的区间个数
			ans += (r - l + 1);
        }
        return ans;
    }
};