第 37A 章　单调队列¶

本章配套 3 道例题，见 §例题。前置：单调栈、队列与双端队列

单调队列是单调栈在滑动窗口上的形态：同样只保留「可能成为答案的候选」，只是多了一条「队首元素会因为滑出窗口而过期」。用一句话概括就是 单调队列 = 单调栈 + 队首按位置过期。

它解决两类题：所有长度为 \(k\) 的窗口的最值，以及转移窗口固定的 DP （\(f_i = \min_{j \in [i-k,\,i-1]} f_j + w(i)\)）。两类都从 \(O(nk)\) 降到 \(O(n)\)。

1　它解决什么问题¶

给定长度为 \(n\) 的序列，求出每一个长度为 \(m\) 的区间内的最小值。

m = 2
7 8 1 4 3 2
  7 1 1 3 2

推导非常清楚：

这是一个叫做「滑动窗口」的技巧。假设已经处理了一个长度为 \(m\) 的区间 \([l, r]\)，在右边加入一个元素得到 \([l, r+1]\)，然后从左边删除一个数字就得到了下一个区间 \([l+1, r+1]\)。 加入一个数字求最小值很简单，删除一个数字就没那么简单了。

注意到只会从左边删除，考虑在区间内维护一个从左至右递增的队列，相当于是最小值的候选队，队首就是当前的最小值。如果最小值被删除，它后面一位就是能够顶替它的新的最小值。右边加入元素可以像之前单调栈那样维护队列的单调性。

还有两条关键结论：

单调队列中的元素不仅值单调，在原序列中的位置也单调；

原序列中在单调队列中相邻的两个元素之间的所有元素的值都比这两个元素小。

第 1 条是「能从队首按位置弹出过期元素」的依据；第 2 条解释了「为什么弹掉的元素永远不会成为答案」。

2　单调队列 = 单调栈 + 队首过期¶

	单调栈	单调队列
尾部（新元素来了）	弹掉破坏单调性的	弹掉破坏单调性的
头部	不动	弹掉超出窗口的
答案在哪	弹栈的瞬间	队首
容器	`list`	`deque` 或 `list` + 头指针

方向记忆：求窗口最大值 → 队列单调递减（队首最大）；求窗口最小值 → 队列单调递增（队首最小）。和单调栈一致：目标与单调性相反。

3　模板：滑动窗口最值¶

from collections import deque


def sliding_max(a, k):
    """每个长度为 k 的窗口的最大值，O(n)。返回长度 n-k+1 的列表。"""
    # 队列存下标而非值：判断队首有没有滑出窗口，只能拿下标和 i 比
    q = deque()                              # 存下标，对应值单调递减
    res = []
    for i, x in enumerate(a):
        # 队尾弹出：比新元素小的旧下标既不更大又更早出窗口，永远不会是答案
        # 用 <= 相等也弹，队列更短；用 < 保留相等元素，最大值答案相同
        while q and a[q[-1]] <= x:           # 队尾比新元素小 -> 永远轮不到它
            q.pop()
        q.append(i)
        # 队首过期：窗口是 [i-k+1, i]，下标 <= i-k 的已经滑出左端
        # 每步窗口只右移一格，至多一个下标过期，所以 if 就够，不必 while
        if q[0] <= i - k:                    # 队首过期
            q.popleft()
        if i >= k - 1:                       # 前 k-1 步窗口没满，不产生答案
            res.append(a[q[0]])              # 队首下标对应的值就是窗口最大值
    return res


def sliding_min(a, k):
    """每个长度为 k 的窗口的最小值，O(n)。"""
    q = deque()                              # 单调递增
    res = []
    for i, x in enumerate(a):
        # 求最小值只需把队尾弹出条件反向：比新元素大的旧下标出局
        while q and a[q[-1]] >= x:
            q.pop()
        q.append(i)
        if q[0] <= i - k:                    # 队首过期判断与求最大值时完全一样
            q.popleft()
        if i >= k - 1:
            res.append(a[q[0]])              # 递增队列的队首是窗口最小值
    return res

⚠️ 一个经典 bug：
while(a[i]>a[q.back()]) q.pop_back();      // 没判队空！
队列被弹空后 q.back() 是未定义行为。Python 里对应写法必须是 while q and a[q[-1]] <= x:——短路求值是免费的保险，一个字都不能省。

陷阱：队首过期的判断是 q[0] <= i - k（下标从 0 开始时），也就是「队首下标已经不在 \([i-k+1, i]\) 内」。写成 q[0] < i - k 会少弹一个，窗口变成 \(k+1\) 长。 写完必须用 \(k=1\) 和 \(k=n\) 两个极端情况自测。

4　性能版：`list` + 双指针¶

\(n \ge 10^6\) 时，deque 的方法调用开销会成为瓶颈。改用 list + 头尾指针：

def sliding_max_fast(a, k):
    """n >= 1e6 时的性能写法：list 当环形/线性缓冲，两个整数指针当队首队尾。

    比 deque 版快约 1.5-2 倍：
      - q[h] / q[t] 是 list 索引，O(1) 且没有块跳转；
      - 全部操作是整数算术，没有方法调用。
    """
    n = len(a)
    q = [0] * n                              # 存下标；队内至多 n 项，一次开满不再扩容
    h = 0                                    # 队首（含）
    t = -1                                   # 队尾（含）；t < h 即队列为空
    res = []
    push = res.append                        # 绑成局部名，省掉每次的属性查找
    for i in range(n):
        x = a[i]
        # t >= h 就是 deque 版的 while q，判空退化成两个整数比较
        while t >= h and a[q[t]] <= x:
            t -= 1                           # 退指针代替 pop，旧值留在原地无需清理
        t += 1
        q[t] = i
        if q[h] <= i - k:                    # 队首下标滑出窗口，进指针代替 popleft
            h += 1
        if i >= k - 1:                       # 窗口凑满 k 个元素才输出
            push(a[q[h]])
    return res

写法	相对速度	可读性
`deque`	1×	✅ 好
`list` + 双指针	1.5–2×	⚠️ 一般

\(n \le 2\times10^5\) 用 deque 就够；\(n \ge 10^6\) 直接上双指针版。

5　单调队列优化 DP¶

这是单调队列真正的威力所在。识别特征：

转移方程形如 \(f_i = \min/\max\limits_{j \in [i - k,\ i - 1]} \{ f_j + w(i) \}\)，其中 \(w(i)\) 只和 \(i\) 有关（与 \(j\) 无关）。

因为 \(w(i)\) 提得出来，所以要求的就是「\(f\) 在一个滑动窗口内的最值」——正是单调队列的活。

\(O(nk)\) \(\Rightarrow\) \(O(n)\)。

from collections import deque


def dp_with_monoqueue(n, k, w):
    """f[i] = min(f[j] for j in [i-k, i-1]) + w[i]，O(n)。"""
    INF = float("inf")
    f = [INF] * (n + 1)
    f[0] = 0                                 # 边界：起点代价为 0，其余待求
    q = deque([0])                           # 存下标，f 值单调递增
    for i in range(1, n + 1):
        # 决策窗口是 [i-k, i-1]，左端 i-k 可取，所以判断是 < 而非滑窗模板的 <=
        while q and q[0] < i - k:            # 队首过期
            q.popleft()
        # 队首是窗口内 f 最小的决策点；w[i] 与决策 j 无关，直接加在括号外
        f[i] = f[q[0]] + w[i]
        # f[i] 求完才入队：i 只能当 i+1 及以后的决策，不能拿来更新自己
        while q and f[q[-1]] >= f[i]:        # 维护单调性
            q.pop()
        q.append(i)
    return f[n]

典型题型：

题型	转移
跳格子（每次跳 \(1..k\) 步）	\(f_i = \min_{j \in [i-k, i-1]} f_j + c_i\)
多重背包的单调队列优化	按余数分组后是滑动窗口最值
最大子段和（长度 \(\le k\)）	\(f_i = \max_{j \in [i-k, i-1]} (S_i - S_j)\)
修剪草坪、烽火传递	同构

详见 DP优化与背包问题。

再往上一层是斜率优化：当 \(w\) 同时依赖 \(i\) 和 \(j\)（形如 \(f_j + a_i b_j\)）时，单调队列要升级成「维护决策点的下凸壳」。原理是一样的——及时扔掉永远不可能最优的决策，只是判断依据从「值的大小」变成了「斜率」。见 DP优化。

6　例题¶

题号	题名	难度	题解
BISHI114	【模板】滑动窗口	简单	题解
BM45	滑动窗口的最大值	较难	题解
LC239	滑动窗口最大值	困难	题解

BISHI114 【模板】滑动窗口（简单）¶

长度 \(n \le 2\times10^5\) 的数组和窗口大小 \(k\)，求每个窗口 \([i, i+k-1]\) 内元素的最大值，共 \(n-k+1\) 个，用单个空格分隔输出。题面见原题。

单调队列的裸模板。

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = list(map(int, data[2:2 + n]))
    # 队列存下标：判断队首是否滑出窗口只能靠下标，值本身给不出位置信息
    q = deque()
    res = []
    # 局部名绑定 append，省掉 n 次属性查找
    push = res.append
    for i in range(n):
        x = a[i]
        # 队尾弹出：值不超过 x 的旧下标既不更大又先出窗口，不可能再当答案
        # 用 <= 相等也弹，队列更短；用 < 保留相等元素，最大值答案一样
        while q and a[q[-1]] <= x:
            q.pop()
        q.append(i)
        # 队首过期：窗口是 [i-k+1, i]，下标 <= i-k 的已滑出左端
        # 每步只右移一格，至多一个下标过期，用 if 而非 while
        if q[0] <= i - k:
            q.popleft()
        # 前 k-1 步窗口尚未凑满 k 个元素，不产生答案
        if i >= k - 1:
            # 队首恰是刚入队的 i 时直接用局部变量 x，省一次列表索引
            push(x if q[0] == i else a[q[0]])
    sys.stdout.write(" ".join(map(str, res)) + "\n")


main()

复杂度 \(O(n)\)。\(n = 2\times10^5\)，时限「其他语言 6 秒」，非常宽裕。

三个坑：

输出用空格分隔在一行（题面样例是一行），不是每行一个。看清楚输出描述能省一次 WA；
样例 2 是 \(k=1\)（每个窗口就是自己），样例 3 是 \(k=n\)（只有一个窗口）—— 出题人专门给了两个边界样例，写完必须都测；
队尾弹出条件用 <=（相等也弹）能让队列更短，用 < 也对但队列会变长。本题求最大值，两者答案相同。

暴力对照：\(O(nk)\) 在 \(n = 2\times10^5, k = 10^5\) 时是 \(2\times10^{10}\)，必然 TLE。而 max(a[i:i+k]) 这种写法虽然是 C 层循环，也是 \(O(nk)\) 的总量，同样过不了。 「切片 + max」看起来很 Pythonic，但复杂度没变——这是初学者最容易犯的错。

题解：solutions/nowcoder/BISHI114/sol.py（已通过判题机验证）

BM45 滑动窗口的最大值¶

与 BISHI114 是同一道题的两种题面：给定长度 \(n\) 的数组与窗口大小 \(k\)，输出每个窗口的最大值。§3 的模板原样可用，唯一要当心的是窗口大小的边界—— 题面允许 \(k > n\)，这种情况下答案是空数组，模板里「窗口填满前不产出」的那个判断（i >= k - 1 才开始写答案）恰好覆盖了它，不需要额外特判。

顺带一提，这题也可以用堆做：把 \((-a_i, i)\) 全丢进小根堆，每次取堆顶时把下标已经滑出窗口的元素懒删除掉。复杂度 \(O(n\log n)\)，比单调队列的 \(O(n)\) 差一个 \(\log\)，但代码短三行—— \(n \le 10^5\) 时两者都过得去，\(n\) 到 \(10^6\) 就只剩单调队列这一条路。

LC239 滑动窗口最大值¶

LC 239. 滑动窗口最大值与滑动窗口的最大值是同一道题，模板一节已经给出解法。补一条上面没说的路：窗口长度固定为 \(k\) 时还能分块预处理—— 把数组按 \(k\) 切块，分别求出每块的前缀最大与后缀最大，任何一个长为 \(k\) 的窗口最多跨两块，答案就是「左块的后缀最大」与「右块的前缀最大」取大者。两遍扫描 \(O(n)\)、额外空间 \(O(n)\)，与单调队列同阶；区别在于它不能在线：整段数组必须先拿到手，而单调队列可以边读边出答案。

7　本章速查¶

要点	结论
核心思想	单调栈 + 队首按位置过期
复杂度	\(O(n)\)，每个元素最多进出一次（均摊）
求窗口最大	队列递减，队首是答案
求窗口最小	队列递增
队首过期判断	`q[0] <= i - k`（0-indexed）；用 \(k=1\)、\(k=n\) 自测
弹队尾前	一律 `while q and ...`，短路判空
\(n \le 2\times10^5\)	用 `deque`，可读性优先
\(n \ge 10^6\)	用 `list` + 双指针，快 1.5–2 倍
`max(a[i:i+k])`	仍是 \(O(nk)\)，不是优化
优化 DP 的适用形	\(f_i = \min_{j\in[i-k,i-1]} f_j + w(i)\)，\(w\) 与 \(j\) 无关
\(w\) 同时依赖 \(i,j\)	升级成斜率优化（凸壳）

识别信号 → 想到什么
「所有长度为 \(k\) 的窗口的最值」
DP 转移是固定长度窗口的最值

「左右第一个更大/更小」「直方图矩形」这类信号见单调栈章末。

第 37A 章 单调队列¶

1 它解决什么问题¶

2 单调队列 = 单调栈 + 队首过期¶

3 模板：滑动窗口最值¶

4 性能版：list + 双指针¶

5 单调队列优化 DP¶

6 例题¶