2762. 不间断子数组

题目链接：https://leetcode.cn/problems/continuous-subarrays/

代码

/**
 * 2762. 不间断子数组
 * https://leetcode.cn/problems/continuous-subarrays/
 */

function continuousSubarrays(nums: number[]): number {
    let left = 0;
    let res = 0;
    const maxQ: number[] = [];
    const minQ: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        while (maxQ.length && maxQ[maxQ.length - 1] < x) {
            maxQ.pop();
        }
        maxQ.push(x);
        while (minQ.length && minQ[minQ.length - 1] > x) {
            minQ.pop();
        }
        minQ.push(x);
        while (maxQ[0] - minQ[0] > 2) {
            if (nums[left] === maxQ[0]) maxQ.shift();
            if (nums[left] === minQ[0]) minQ.shift();
            left++;
        }
        res += i - left + 1;
    }
    return res;
}

思路

滑动窗口 + 单调队列维护窗口内的最大值和最小值：

1. 使用两个单调队列：

   • maxQ：单调递减队列，维护窗口内的最大值（队首为最大值）
   • minQ：单调递增队列，维护窗口内的最小值（队首为最小值）

2. 对于每个右端点 i：

   • 将 nums[i] 加入两个队列，维护单调性
   • 当 maxQ[0] - minQ[0] > 2 时，收缩左边界 left，并更新队列
   • 以 i 为右端点的所有有效子数组数量为 i - left + 1

3. 累加所有右端点对应的子数组数量

• 时间复杂度 $O(n)$，每个元素最多入队和出队一次
• 空间复杂度 $O(n)$，单调队列最多存储 $n$ 个元素