1、先看暴力解法的问题#

假设数组是：

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

每个长度为 3 的窗口最大值依次是：

1
[1, 3, -1] -> 3
2
[3, -1, -3] -> 3
3
[-1, -3, 5] -> 5
4
[-3, 5, 3] -> 5
5
[5, 3, 6] -> 6
6
[3, 6, 7] -> 7

暴力写法很容易理解：

1
def max_sliding_window(nums, k):
2
    ans = []
3
    for i in range(len(nums) - k + 1):
4
        ans.append(max(nums[i:i + k]))
5
    return ans

但这里每个窗口都重新 max 一次。窗口之间明明有大量重叠元素，却没有复用之前的信息。

2、队列里应该保存什么#

单调队列通常保存下标，而不是直接保存数值。原因是我们既要比较大小，也要判断元素是否已经滑出窗口。

比如当前遍历到下标 i，窗口左边界是：

1
left = i - k + 1

如果队头下标小于 left，说明它已经不在窗口里，需要弹出。

3、为什么要保持单调递减#

我们想快速得到窗口最大值，所以队头应该对应当前窗口中最大的数。为了做到这一点，队列里的值可以保持从大到小。

当新元素 nums[i] 进来时，如果队尾对应的值比它小，那么队尾元素以后也不可能成为最大值：

• 它比新元素小。
• 它还比新元素更早离开窗口。

所以可以直接从队尾弹掉。

1
while q and nums[q[-1]] <= nums[i]:
2
    q.pop()

这一步是单调队列的核心。

4、完整代码#

用 collections.deque 写起来比较清楚：

1
from collections import deque
2

3
def max_sliding_window(nums, k):
4
    q = deque()
5
    ans = []
6

7
    for i, x in enumerate(nums):
8
        left = i - k + 1
9

10
        while q and q[0] < left:
11
            q.popleft()
12

13
        while q and nums[q[-1]] <= x:
14
            q.pop()
15

16
        q.append(i)
17

18
        if i >= k - 1:
19
            ans.append(nums[q[0]])
20

21
    return ans

这里的 q[0] 始终是当前窗口最大值的下标。只有当窗口已经形成，也就是 i >= k - 1 时，才把答案加入列表。

5、用一个窗口走一遍#

还是看这个数组：

1
nums = [1, 3, -1]

遍历到 1 时，队列为空，直接加入下标 0。

遍历到 3 时，队尾的 1 比 3 小，弹出下标 0，再加入下标 1。此时队头就是 3。

遍历到 -1 时，队尾的 3 比 -1 大，不弹出，加入下标 2。窗口形成后，队头仍然是下标 1，对应最大值 3。

这个过程说明，队列里不需要保存窗口内所有元素，只保留“未来可能成为最大值”的候选下标。

6、常见边界检查#

写单调队列时，我会特别检查这几个地方：

• 队列保存的是下标，不是值。
• 先移除滑出窗口的队头。
• 再从队尾移除不可能成为答案的元素。
• 窗口长度达到 k 后再记录答案。
• 比较时使用 < 还是 <= 要保持一致。

在滑动窗口最大值里，我通常写 nums[q[-1]] <= x，这样相同值时保留更新的下标，过期判断会更自然。

小结#

单调队列可以理解为“带淘汰规则的候选答案队列”。它不是为了保存所有窗口元素，而是为了让队头随时代表当前窗口的最大值。

对我来说，掌握这个结构的关键是两句话：过期的下标从队头走掉，更弱的候选从队尾删掉。只要这两步写清楚，滑动窗口最大值这类题就会稳定很多。