单调队列

2026-06-02

滑动窗口最大/最小值 的关键 — 把窗口里以后永远不可能成为答案的元素提前丢掉。一句话讲完: 新人比队尾大,队尾就该退休;窗口左端滑出去,队头就该过期。每个元素最多进队一次出队一次,总 。

直觉 — 把”不可能成为答案的元素”丢掉

暴力做滑动窗口最大值: 每移一步重扫 k 个数,。慢在哪? 重复看了一堆”已经被压住、再也翻不了身”的数。

考虑 [1, 3, -1, ...], 窗口 k=3。新元素 3 进来时, 前面的 1 还有意义吗? 在 3 还活着的窗口里, 1 永远比 3 小, 永远轮不到它当最大值; 等 3 过期了, 1 早就跟着过期了。所以 1 可以立即扔掉,扔得越早越省事。

这就是单调队列的全部哲学:

  • 从队尾入队: 新元素 x 进来, 把 <= x 的队尾元素全弹掉(它们这辈子都被 x 压住了)。
  • 从队头取答案: 维护完单调性后, 队头永远是当前窗口最大值。
  • 从队头过期: 如果队头下标已经滑出窗口, popleft 掉。

因为两端都要操作, 所以底层是 deque(双端队列), 不是普通栈或队列。每个元素入队一次、出队一次, 摊还 , 全程 。

关键洞察: 队列里存的不是”窗口里的所有元素”,而是未来还可能成为最大值的候选者。一个严格递减的栈。

动画 — 跟着四步走

数组 [1, 3, -1, -3, 5, 3, 6, 7], k=3。每点一次”下一步”,看四种颜色:

  • 绿色 (current): 当前访问的新元素
  • 橙色 (cleaned): 队尾被新人打败、弹出
  • 红色 (expired): 队头下标过期、popleft
  • 青色 (in-queue): 当前还在 deque 里的候选者

特别盯住 5 那一帧: 它一进来, 队尾的 -3、-1 直接全清空, 因为它们这辈子都翻不过 5 了。这一下就是 摊还的精髓。

模板 — Python deque, 滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque

def max_sliding_window(nums, k):
    q = deque()           # 存下标, 对应的值从队头到队尾严格递减
    ans = []
    for i, x in enumerate(nums):
        # ① 队尾维护单调性: 新人打旧人
        while q and nums[q[-1]] <= x:
            q.pop()
        # ② 入队
        q.append(i)
        # ③ 队头维护窗口: 过期的出局
        if q[0] <= i - k:
            q.popleft()
        # ④ 取答案: 队头就是最大值
        if i >= k - 1:
            ans.append(nums[q[0]])
    return ans

三个易错点:

  1. 存下标, 不存值。 因为队头过期判断 q[0] <= i - k 必须靠下标。
  2. 顺序不能乱。 入队必须在清理队尾之后(否则新元素可能被自己清掉);取答案必须在所有清理之后。
  3. 求最小值就把 <= 改成 >=,队列变递增, 其它一字不差。

三步走口诀: ① 队尾清理被打败的 → ② 入队 → ③ 队头清理过期的 → ④ 队头取答案。

单调栈 vs 单调队列 — 一字之差

两者都是”用单调性扔掉没用的”, 区别在有没有窗口约束。

维度 单调栈 单调队列
结构 栈(只一端) deque(两端)
解决问题 下一个更大/更小元素 滑动窗口最值
看的范围 无限往后看 限定窗口 k
队头操作 不需要 过期淘汰
答案在哪 出栈时确定 队头即答案
复杂度

一句话: 单调栈 = 窗口无限大的单调队列。多出来的”队头清理”操作, 就是为窗口约束付出的代价。

经典题 — 239. Sliding Window Maximum

给定数组 nums 和窗口大小 k, 返回每个滑动窗口的最大值。

直接套模板, 上面的 max_sliding_window 就是 AC 代码。复杂度 , 暴力 在 时直接 TLE。

其他必刷:

判断信号: 题目里出现”窗口大小 k”、”长度不超过 k 的子数组最值”、”DP 转移依赖前 k 项最值”,条件反射上单调队列。

记忆法

一句话: 能压住你的, 早晚轮不到你;能等到你的, 你也早过期了。

三步标准动作:

  1. 新元素从队尾进, 把比它小的队尾全弹掉(队尾打架)
  2. 队头如果下标过期, popleft(队头退休)
  3. 队头就是窗口最值(队头领奖)

判题速查:

  • 只问”下一个更大” → 单调栈
  • 限定窗口求最值 → 单调队列
  • 改查交替 / 任意区间最值 → 线段树 or ST 表

记住一个画面就够: deque 里站着一排严格递减的候选王, 队头那位戴着王冠, 谁过期谁让位, 谁更强谁挤进来。