跳转至

239. 滑动窗口最大值（Sliding Window Maximum）

频次 ★★★★★ · 难度 🔴 · 高频：字节/阿里/美团

题目

长度 k 的窗口从左到右滑过数组，输出每个位置的窗口最大值。

示例： 

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]

思路

单调递减双端队列（存下标）：

  • 队头永远是当前窗口最大值的下标
  • 新元素入队前，从队尾弹掉所有比它小的——它们在新元素在场期间永无出头之日
  • 队头下标滑出窗口范围（<= i - k）时从队头弹出

每个下标进出队各一次，O(n)。

代码

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();   // 存下标,对应值单调递减
    int n = nums.length;
    int[] res = new int[n - k + 1];
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i])
            dq.pollLast();                     // 弹掉"更小且更旧"的
        dq.offerLast(i);
        if (dq.peekFirst() <= i - k) dq.pollFirst();  // 队头滑出窗口
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

复杂度

  • 时间：O(n) —— 每个元素至多进队/出队一次
  • 空间：O(k) —— 队列长度不超过窗口

边界条件

  • k = 1：输出原数组
  • k = n：只输出全局最大值
  • 全递减数组：队列长度达到 k，队头持续输出

变式

  • 滑动窗口最小值：队列改单调递增
  • 队列存值而非下标：无法判断队头是否过期，必须存下标——面试常见的追问点
  • 求窗口最大值之和/差：同款队列，只改输出

易错点

  • 弹队尾的条件 <=（相等也弹）：留新不留旧，旧的先过期
  • 判断过期用下标（dq.peekFirst() <= i - k），不能用值——窗口里可能有重复值
  • 出结果的时机是 i >= k - 1，结果下标 i - k + 1
  • 读队头用 peekFirst()，别用 pollFirst()：前者只看不删，后者取出即删除。写成 res[i-k+1] = nums[dq.pollFirst()] 会把当前最大值从队列里弹走，下一个窗口只能拿到次大值（典型症状：示例1 输出 [3,-1,5,3,6,7]）
  • 用 LinkedList 也能当 Deque，但 ArrayDeque 无结点分配开销更快，见集合框架

走查示例（nums=[1,3,-1,-3,5,3,6,7], k=3）

i v ①弹队尾 ②入队后队列(下标:值) ③弹队头 ④res
0 1 — [0:1] 否 —
1 3 弹 0（1≤3） [1:3] 否 —
2 -1 不弹 [1:3, 2:-1] 否 3
3 -3 不弹 [1:3, 2:-1, 3:-3] 否 3
4 5 弹 3、2、1 [4:5] 否 5
5 3 不弹 [4:5, 5:3] 否 5
6 6 弹 5、4 [6:6] 否 6
7 7 弹 6 [7:7] 否 7

i=4 时 5 把 3、-1、-3 全弹光——它们比 5 小且活得更短，再也不可能成为任何窗口的最大值，这就是"压制"。队列的语义是「将来还有资格当窗口最大值的候选下标」，队头即当前窗口最大值。

面试追问

  • 为什么不用大顶堆？ 堆能做但 O(n log n)：过期元素懒删除，堆顶出窗时才弹。单调队列把"过期"和"被压制"两类无用元素都及时清掉才到 O(n)——能对比两种方案取舍再给结论
  • 单调队列和单调栈什么关系？ 都维护单调性淘汰"不可能成为答案"的候选；栈只关心一端（最近的更大/更小），队列因为窗口会过期需要两端操作

关联题