算法 - 滑动窗口最大值

Posted on

1. 题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字，滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值组成的数组。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]

窗口位置                    最大值
---------------           -----
[1  3  -1] -3  5  3  6  7    3
 1 [3  -1  -3] 5  3  6  7    3
 1  3 [-1  -3  5] 3  6  7    5
 1  3  -1 [-3  5  3] 6  7    5
 1  3  -1  -3 [5  3  6] 7    6
 1  3  -1  -3  5 [3  6  7]   7

2. 解题思路

2.1 暴力法

每个窗口遍历求最大，O(n·k)，k 大时超时，仅作对比。

2.2 单调递减双端队列（最优）

维护一个存下标的双端队列，保证队列对应元素值从队头到队尾单调递减，队头始终是当前窗口最大值的下标。

对每个新元素 i：

  1. 淘汰过期：若队头下标已滑出窗口（queue[0] <= i - k），从队头弹出。
  2. 维护单调性：从队尾开始，凡是值 <= nums[i] 的下标全部弹出——它们被 nums[i]「又新又大」地压制，永远不可能再成为答案。
  3. 把 i 入队尾。
  4. 当 i >= k - 1 开始收集答案，队头即当前窗口最大值。
  • 时间复杂度：O(n)，每个元素最多入队出队各一次；空间复杂度：O(k)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const deque: number[] = []; // 存下标，对应值单调递减
    const res: number[] = [];

    for (let i = 0; i < n; i++) {
        // 1. 队头过期（滑出窗口）
        if (deque.length && deque[0] <= i - k) deque.shift();

        // 2. 队尾所有 <= 当前值的元素失去意义，弹出
        while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        // 3. 当前下标入队
        deque.push(i);

        // 4. 窗口形成后收集队头最大值
        if (i >= k - 1) res.push(nums[deque[0]]);
    }

    return res;
}

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

说明：JS 数组的 shift() 是 O(n)，严格最坏复杂度会退化；面试可指出用「头指针 index」模拟队列头、或双向链表实现真正 O(1) 出队。此处为清晰用 shift。

4. 面试延伸

  • 单调栈 vs 单调队列：单调栈解决「下一个更大元素」等；单调队列额外处理「窗口左边界过期」，本题是其模板题。
  • 变形：窗口最小值（改成单调递增队列）、绝对值不超过 limit 的最长子数组等，都基于单调队列。
  • 追问：为什么队列存下标而不是值？因为需要靠下标判断队头是否滑出窗口。
  • 另一路线：分块 / 稀疏表(ST) 预处理区间最大值，也能做到接近 O(n)，可作为思路拓展。

难度：困难 | LeetCode 239 | 单调队列模板