239. 滑动窗口最大值

题目链接：https://leetcode.cn/problems/sliding-window-maximum/

代码

/**
 * 239. 滑动窗口最大值
 * https://leetcode.cn/problems/sliding-window-maximum/
 */

function maxSlidingWindow(nums: number[], k: number): number[] {
    const queue: number[] = []; // 单调递减，存储索引
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        // 若队列最右侧数小于等于新数则将其移出队列，保证单调递减
        while (queue.length && nums[queue[queue.length - 1]] <= nums[i]) {
            queue.pop();
        }
        queue.push(i);
        // 目前最大数该出栈了
        if (i >= queue[0] + k) {
            queue.shift();
        }
        // 初始化第一个窗口后再记录最大值
        if (i >= k - 1) {
            res.push(nums[queue[0]]);
        }
    }
    return res;
}

// 测试
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

思路

使用单调队列（deque）：

队列中存的是下标，队头始终是当前窗口的最大值下标；
新元素入队前，将队尾所有小于等于它的元素弹出，保证队列从队头到队尾对应的数是单调递减的；
每次右指针 i 向右移动时：
- 把 i 入队；
- 如果队头下标已经滑出窗口（i >= queue[0] + k），就把队头弹出；
- 当窗口大小达到 k 时，将队头对应的值压入结果。
时间复杂度 $O (n)$ ，因为每个元素最多进队一次、出队一次
空间复杂度 $O (k)$ ，单调队列最多存储 $k$ 个元素（窗口大小）

239. 滑动窗口最大值 ​

代码 ​

思路 ​

239. 滑动窗口最大值

代码

思路