滑动窗口最大值为什么要用单调队列？和普通双指针有什么区别？

简化版

滑动窗口最大值要在每个长度为 k 的窗口里快速取最大值。用单调递减队列保存候选下标：新元素进来时，把队尾所有小于等于它的下标弹出；队头若滑出窗口就弹出；窗口形成后，队头就是最大值下标。

详细版

普通滑动窗口只能维护和、计数这类可增可减状态，但最大值在左端移出时很难 O(1) 更新。单调队列解决的是“窗口最值”问题：队列里只保留仍在窗口内、且有机会成为最大值的元素下标。

当新元素 nums[right] 进入窗口时，队尾比它小的元素不可能再成为未来窗口最大值，因为新元素更大且位置更靠右、存活更久，所以可以弹出。之后把 right 入队。若队头下标 <= right-k，说明它已经离开窗口，弹出。窗口长度达到 k 后，nums[deque.peekFirst()] 就是当前最大值。

每个下标最多入队一次、出队一次，时间 O(n)，队列空间 O(k)。

完整版教学

一、为什么普通窗口不够

固定窗口求和很简单：右边加一个，左边减一个，O(1) 更新。但最大值不满足这种可逆更新。假设窗口 [9,1,2] 最大是 9，当 9 滑出后，新最大值要从 [1,2] 里重新找。

如果每个窗口都扫描 k 个元素，总复杂度是 O(nk)。当 n=100000, k=500 时，最坏需要约 5000 万次比较，面试中通常希望优化到 O(n)。

记忆钩子：窗口最大值难在“最大值离开后谁接班”，单调队列就是提前排好接班队伍。

二、单调队列保存什么

队列保存的是下标，不直接保存值。原因有两个：第一，要判断队头是否滑出窗口，需要下标；第二，值可以通过 nums[index] 取到。

队列从头到尾对应的值保持递减：

nums:  [1, 3, -1, -3, 5]
deque: [1, 2, 3]  -> values [3, -1, -3]
队头 1 对应当前最大值 3

递减意味着队头永远是当前候选里的最大值。队尾是最弱候选，新元素进来时从队尾清理。

三、新元素为什么能淘汰队尾

如果 nums[right] >= nums[tail]，并且 right 比 tail 更靠右，那么在未来任何同时包含这两个下标的窗口里，新元素都不比旧元素差；当旧元素还没过期时，新元素也在窗口内；旧元素过期后，新元素可能还活着。

所以旧的队尾没有成为最大值的机会，可以弹出。这个支配关系可以写成：

right > tail 且 nums[right] >= nums[tail]
=> tail 被 right 支配
=> tail 不可能成为当前或未来窗口最大值

这就是单调队列能保持线性的原因。每个元素只会被更强的新元素弹出一次。

四、代码模板

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();

    for (int right = 0; right < n; right++) {
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[right]) {
            dq.pollLast();
        }
        dq.offerLast(right);

        if (dq.peekFirst() <= right - k) {
            dq.pollFirst();
        }

        if (right >= k - 1) {
            ans[right - k + 1] = nums[dq.peekFirst()];
        }
    }
    return ans;
}

用 <= 弹队尾可以让相同值保留更新的下标，过期判断更干净；用 < 也能做，但队列里会保留更多相等元素。

五、数字例子

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

right	新值	队列值	当前最大
0	1	[1]	窗口未满
1	3	[3]	窗口未满
2	-1	[3,-1]	3
3	-3	[3,-1,-3]	3
4	5	[5]	5

当 5 进入时，队尾 -3、-1、3 都被弹出，因为 5 更大且更靠右。后续窗口只要包含 5，它们都不可能当最大值。

六、和堆做法的对比

做法	时间复杂度	空间	关键维护
每窗扫描	O(nk)	O(1)	无
最大堆	O(n log n)	O(n)	堆顶过期下标
单调队列	O(n)	O(k)	递减候选队列

堆也能做，但过期元素会滞留在堆里，需要懒删除。单调队列更贴合滑动窗口，因为它只保留窗口内有竞争力的候选。

七、常见误区与追问

误区：队列里保存值就够了。 需要下标判断是否过期，只存值会处理不了重复值和窗口边界。
误区：队头过期条件写成 < right-k。 当下标等于 right-k 时已经在窗口左边之外，应弹出。
误区：新元素只入队，不清理队尾。 队列不单调时，队头不再保证最大。
追问：为什么每个元素最多出队一次？ 它要么从队尾被更大元素弹出，要么从队头过期弹出，不会反复进出。
追问：最小值窗口怎么改？ 把队列维护成递增，队头就是最小值。
追问：k=1 时结果是什么？ 每个窗口只有自己，结果等于原数组；模板也自然成立。

八、加强记忆

滑动窗口最大值的核心是“候选最大值队伍”。队列存下标，值保持递减；右边新元素进来时淘汰队尾弱候选，左边过期时弹队头。窗口形成后队头就是最大值。普通双指针负责窗口边界，单调队列负责窗口最值，这就是它比普通窗口多出来的结构。

简化版

详细版