如何用单调队列求滑动窗口最大值？

简化版

滑动窗口最大值用单调递减双端队列存下标：队头永远是当前窗口最大值候选，队尾弹掉比新元素小的下标，队头弹掉已经滑出窗口的下标。每个元素最多进出队一次，时间 O(n)，空间 O(k)。

详细版

窗口大小为 k，每次右端加入一个新元素。为了快速得到最大值，队列中只保留仍可能成为最大值的下标，并让对应值从队头到队尾递减。新元素进入前，所有比它小的队尾元素都不可能再成为未来窗口最大值，可以删除。

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) deque.pollLast();
        deque.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = nums[deque.peekFirst()];
    }
    return ans;
}

注意队列存下标，既能比较值，也能判断是否过期。队头不是永久最大值，只是当前窗口内最大候选。

完整版教学

一、为什么普通队列不够

普通队列只知道先来后到，不能快速回答“窗口里谁最大”。如果每个窗口都重新扫描 k 个元素，数组长度 n 时复杂度是 O(nk)。当 n=100000, k=5000，比较次数接近 5 亿，面试中通常不能接受。

单调队列的目标是让最大值始终在队头。它不是把窗口完全排序，而是删除那些已经不可能成为答案的元素。

二、单调队列维护两个条件

第一个条件是范围有效：队头下标必须在当前窗口 [i-k+1, i] 内。第二个条件是值单调：队列中下标对应的值从队头到队尾递减。满足这两个条件时，队头就是窗口最大值。

窗口 [i-k+1, i]
队头 ---------------- 队尾
最大候选  次大候选  更晚但更小的候选

如果队头过期，就从头删；如果新元素比队尾大，就从尾删。双端队列正好支持这两端操作。

三、为什么可以删掉队尾小元素

假设队尾下标是 j，当前下标是 i，且 nums[i] >= nums[j]。因为 i 比 j 更靠右，所以在未来窗口中，只要 j 还没过期，i 也一定还没过期；同时 nums[i] 又不小于 nums[j]。因此 j 永远不可能比 i 更适合作为最大值，可以安全删除。

例如窗口大小 3，数组片段 [1,3,-1] 中，当 3 到来时，1 会被删除；后续只要包含 1 的窗口也包含 3，1 就不可能是最大值。

四、手算示例

以 nums=[1,3,-1,-3,5,3,6,7], k=3 为例：

i	当前值	队列对应值	输出
0	1	[1]	-
1	3	[3]	-
2	-1	[3,-1]	3
3	-3	[3,-1,-3]	3
4	5	[5]	5
5	3	[5,3]	5
6	6	[6]	6
7	7	[7]	7

输出是 [3,3,5,5,6,7]。队列中保存的是下标，表格为了直观展示成对应值。

五、代码顺序为什么重要

常见写法先删除过期队头，再删除队尾较小元素，最后加入当前下标并在窗口形成后输出。过期判断是 deque.peekFirst() <= i - k，因为当前窗口左边界是 i-k+1。

当前 i = 5, k = 3
窗口左边界 = 3
下标 <= 2 都过期，即 <= i-k

如果忘记过期删除，队头可能还停留在窗口外，答案会偏大且很难从局部测试中发现。

六、常见误区与追问

记忆钩子：单调队列的队头管“答案”，队尾管“竞争淘汰”，下标管“是否过期”。

误区：单调队列是把窗口排序。 它只保留有机会成为最大值的候选，不维护全量有序列表。
误区：队列里存值就可以。 有重复值和过期判断时必须依赖下标，存值容易删错。
误区：队尾小于当前值才删，等于不删。 <= 可以删除旧的相等值，让更新的下标保留更久；用 < 也可但队列会更长。
追问：为什么复杂度是 O(n)？ 每个下标最多入队一次、从队头或队尾出队一次，总操作线性。
追问：求滑动窗口最小值怎么改？ 队列改为单调递增，队头保存最小候选。
追问：和堆做法相比如何？ 堆是 O(n log k)，还要懒删除过期元素；单调队列利用窗口顺序做到 O(n)。

七、加强记忆

滑动窗口最大值要记住三个动作：删过期、删队尾小值、加当前并读队头。单调队列不是排序器，而是候选淘汰器；新元素更大且更晚，旧小值就再也没有翻身机会。把“范围有效”和“值递减”两个不变量守住，代码自然就稳。

简化版

详细版