第 37 章 单调栈与单调队列¶
配套例题：BISHI121 数列后缀极大位置统计、BISHI122 区间后缀极大位置计数、BISHI114 【模板】滑动窗口 来源：S3 day1《栈 队列》单调栈 ＆ 单调队列；S3 day6《单调队列》（HZC）；S3 day4
deque(更正).cpp前置：32-栈、33-队列与双端队列
单调栈和单调队列是同一个思想的两种形态：
维护一个「有可能成为未来答案的候选集合」， 把那些「已经被证明永远不可能成为答案」的元素及时扔掉。
它们把很多 \(O(n^2)\) 的暴力降到 \(O(n)\)，而且实现只有几行。 这是竞赛里性价比最高的技巧之一。
37.1 单调栈¶
它解决什么问题¶
给定长为 \(n\) 的序列，求每个元素右边第一个比它小的元素。没有则输出 0。 \(n \le 10^6\)。（S3 day1 原题）
暴力是 \(O(n^2)\)。单调栈的思路（照抄课件）：
维护一个单调递增的栈，从左至右遍历序列。 考虑当前处理到元素 \(x\)，栈顶元素为 \(y\)。 如果 \(x < y\)，那么可以知道 \(y\) 右边第一个比 \(y\) 小的元素就是 \(x\)。 所以 \(y\) 的答案就计算出来了，可以将 \(y\) 从栈中弹出。 如此处理之后，要么栈已经空了，要么栈顶元素 \(y \le x\)。 将 \(x\) 压入栈中，栈中元素依然保持单调递增。 遍历完毕后，栈中剩下的元素均无答案。时间复杂度 \(\Theta(n)\)。
复杂度为什么是 \(O(n)\)？ 每个元素最多入栈一次、出栈一次，
所以内层的 while 循环总共只会执行 \(O(n)\) 次——这是均摊分析，
和 list.append 的均摊 \(O(1)\) 是同一类论证（30-序列与数组）。
四种方向的对照表¶
这是最容易记混的地方。记住两条规则：
- 求「更大」用递减栈，求「更小」用递增栈（栈的单调性和目标相反）；
- 求右边就正序扫，求左边就倒序扫。
| 目标 | 扫描方向 | 栈的单调性 | 弹栈条件（a[st[-1]] vs a[i]） |
|---|---|---|---|
| 右边第一个更大 | 正序 | 递减 | <= a[i] 弹 |
| 右边第一个更小 | 正序 | 递增 | >= a[i] 弹 |
| 左边第一个更大 | 倒序 | 递减 | <= a[i] 弹 |
| 左边第一个更小 | 倒序 | 递增 | >= a[i] 弹 |
严格 vs 非严格：弹栈条件用
<=还是<，决定了「相等元素」怎么处理。 - 用<=（弹掉相等的）：得到的是「第一个严格更大的」； - 用<（保留相等的）：得到的是「第一个大于等于的」。有重复元素的题目一定要想清楚这一位，这是单调栈最常见的 WA 来源。
模板¶
def next_greater(a):
"""对每个 i，求右边第一个严格大于 a[i] 的下标；不存在则为 -1。O(n)。"""
n = len(a)
res = [-1] * n # 默认 -1，表示右边没有更大的元素
# 栈里存下标不存值：答案要写回 res[下标]，宽度、距离一类的量也只能靠下标算
st = [] # 存下标，对应的值单调递减
for i in range(n):
ai = a[i]
# 条件是 < 而不是 <=：相等时不弹，于是求出的是「第一个严格更大的」
while st and a[st[-1]] < ai: # 栈顶被 a[i] 顶掉，答案就是 i
res[st.pop()] = i # 弹出即定案，每个下标只结算这一次
st.append(i) # 压入后栈内自底向上不增（相等元素并存）
return res
def prev_smaller(a):
"""对每个 i，求左边第一个严格小于 a[i] 的下标；不存在则为 -1。O(n)。"""
n = len(a)
res = [-1] * n
st = [] # 存下标，对应的值单调递增
for i in range(n):
ai = a[i]
# 弹掉所有不小于 a[i] 的栈顶：它们不满足「严格小于」；
# 而对 i 右边的元素来说 a[i] 又更近又不更大，这些栈顶再也轮不到
while st and a[st[-1]] >= ai:
st.pop()
# 栈空说明左边所有元素都不小于 a[i]，答案保持 -1
res[i] = st[-1] if st else -1 # ★ 弹完之后栈顶就是答案
st.append(i) # i 成为后续元素的候选前驱
return res
两种写法的区别： -
next_greater：在弹栈时给被弹出的元素赋答案（「我被谁顶掉了」）； -prev_smaller：弹完之后看栈顶给当前元素赋答案（「谁挡在我前面」）。求「右边的」用前者，求「左边的」用后者，都只需要正序扫一遍， 不需要真的倒着扫。这比上面那张表更实用。
经典应用：直方图中最大矩形¶
给定柱状图，求其中面积最大的子矩形。（S3 day1 例题）
课件的思路：
以每个柱子做高，向左和向右分别找出第一个比它矮的柱子， 这个是能覆盖的极大子矩形。可以使用正反两次单调栈扫描完成。
def largest_rectangle(h):
"""直方图最大矩形面积，O(n)。
技巧：在两端各加一个高度 -1 的哨兵，
就不用单独处理「栈没被弹空」和「左边界不存在」两种边界情况。
"""
# 首哨兵比任何柱子都矮，永远不会被弹出，栈因此永远非空，省掉 if st
# 尾哨兵同样矮，扫到它时会把栈里剩下的柱子全部弹出结算，省掉收尾循环
a = [-1] + list(h) + [-1]
st = [] # 存下标，对应高度单调递增
best = 0
for i, x in enumerate(a):
# 栈顶比 x 高，说明它向右扩不过 i，此刻正好能算出它的极大矩形
# 条件用 > 不用 >=：等高的柱子留给最右边那根一次结算，宽度不会算漏
while st and a[st[-1]] > x:
top = st.pop()
# 左右边界都是「第一个比它矮的」，两端都取不到，所以宽度再减 1
width = i - st[-1] - 1 # 左边界是新栈顶，右边界是 i
area = a[top] * width # 以 a[top] 为高时能覆盖的最大矩形
if area > best:
best = area
st.append(i)
return best
哨兵是单调栈的标配技巧。开头放 \(-\infty\) 保证栈永远非空（省掉
if st）， 结尾放 \(-\infty\) 保证所有元素最终都被弹出（省掉收尾循环）。
这个模型的变体极多：最大全 1 子矩阵、接雨水、柱状图问题， 都是「向左右找第一个不满足条件的位置」。
37.2 单调队列¶
它解决什么问题¶
给定长度为 \(n\) 的序列，求出每一个长度为 \(m\) 的区间内的最小值。（S3 day1 例题）
课件的推导非常清楚：
这是一个叫做「滑动窗口」的技巧。假设现在我们已经处理了一个长度为 \(m\) 的区间 \([l, r]\)， 在右边加入一个元素得到 \([l, r+1]\)，然后从左边删除一个数字就得到了下一个区间 \([l+1, r+1]\)。 加入一个数字求最小值很简单，删除一个数字就没那么简单了。
注意到我们只会从左边删除，考虑在区间内维护一个从左至右递增的队列， 相当于是最小值的候选队，队首就是当前的最小值。 如果最小值被删除，它后面一位就是能够顶替它的新的最小值。 右边加入元素可以像之前单调栈那样维护队列的单调性。
S3 day6 的《单调队列》课件补了两条关键结论：
- 单调队列中的元素不仅值单调，在原序列中的位置也单调；
- 原序列中在单调队列中相邻的两个元素之间的所有元素的值都比这两个元素小。
第 1 条是「能从队首按位置弹出过期元素」的依据； 第 2 条解释了「为什么弹掉的元素永远不会成为答案」。
单调队列 = 单调栈 + 队首过期¶
| 单调栈 | 单调队列 | |
|---|---|---|
| 尾部（新元素来了） | 弹掉破坏单调性的 | 弹掉破坏单调性的 |
| 头部 | 不动 | 弹掉超出窗口的 |
| 答案在哪 | 弹栈的瞬间 | 队首 |
| 容器 | list |
deque 或 list + 头指针 |
方向记忆：求窗口最大值 → 队列单调递减（队首最大）； 求窗口最小值 → 队列单调递增（队首最小）。和单调栈一致：目标与单调性相反。
模板：滑动窗口最值¶
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
⚠️ S3 day4 的
队列被弹空后deque(更正).cpp里有个经典 bug：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\) 两个极端情况自测。
性能版：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\) 直接上双指针版。
37.3 单调队列优化 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)\) |
| 修剪草坪、烽火传递 | 同构 |
S3 day6 的《单调队列》课件最后讲到斜率优化： 当 \(w\) 同时依赖 \(i\) 和 \(j\)（形如 \(f_j + a_i b_j\)）时，单调队列要升级成 「维护决策点的下凸壳」。原理是一样的——及时扔掉永远不可能最优的决策， 只是判断依据从「值的大小」变成了「斜率」。见 104-DP优化。
37.4 例题¶
BISHI114 【模板】滑动窗口（简单）¶
长度 \(n \le 2\times10^5\) 的数组和窗口大小 \(k\)， 求每个窗口 \([i, i+k-1]\) 内元素的最大值，共 \(n-k+1\) 个，用单个空格分隔输出。 题面见 BISHI114 原题（牛客）。
单调队列的裸模板。
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/BISHI114.py（已通过牛客判题机验证）
BISHI121 数列后缀极大位置统计（简单）¶
数列 \(a\) 初始为空，\(n \le 10^5\) 次操作每次在末尾添加正整数 \(x\)。 每次操作后，求当前所有后缀最大值下标（下标从 1 开始）的按位异或和。 下标 \(i\) 是后缀最大值下标当且仅当对所有 \(i < j \le |a|\) 都有 \(a_i > a_j\)（严格）。 题面见 BISHI121 原题（牛客）。
核心观察：「后缀最大值下标的集合」就是单调递减栈本身。
为什么？栈中保持严格递减，意味着栈里每个元素都严格大于它右边所有还在栈里的元素； 而被弹出的元素恰恰是「存在右边某个元素 \(\ge\) 它」的，正好不满足条件。
新元素 \(x\) 到来时弹掉所有 \(a_{\text{top}} \le x\) 的（注意 <=，因为条件是严格大于），
再把自己压进去。维护一个异或和变量，随进出增量更新：
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
# 栈里存的就是要输出的下标本身，栈的内容即「后缀最大值下标」的集合
st = [] # 存下标（1-indexed），对应值严格递减
# 增量维护栈内下标的异或和；每次重扫整个栈会退化成 O(n^2)
xor = 0
out = []
push = out.append
for i in range(1, n + 1):
# 题目下标从 1 起、数组从 0 起，取值要错开一位
x = a[i - 1]
# 弹掉所有值不大于 x 的栈顶：它们右边出现了不小于自己的元素，
# 「对右边所有 j 都有 a[i] > a[j]」不再成立
while st and a[st[-1] - 1] <= x: # 相等也要弹（条件是严格大于）
# 异或的自反性：同一个下标再异或一次，等同于把它从集合里移除
xor ^= st.pop()
# 末尾新元素右边没有任何元素，必是后缀最大值，入栈并计入异或和
st.append(i)
xor ^= i
push(xor)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
复杂度 \(O(n)\)（每个下标最多进出一次）。
手动验证样例（a = 2 1 3 5 4）：
| \(i\) | \(x\) | 弹出 | 栈（下标） | 异或和 | 期望 |
|---|---|---|---|---|---|
| 1 | 2 | — | [1] |
1 | 1 ✓ |
| 2 | 1 | — （\(2 > 1\)，不弹） | [1,2] |
\(1 \oplus 2 = 3\) | 3 ✓ |
| 3 | 3 | 2、1 | [3] |
3 | 3 ✓ |
| 4 | 5 | 3 | [4] |
4 | 4 ✓ |
| 5 | 4 | — （\(5 > 4\)） | [4,5] |
\(4 \oplus 5 = 1\) | 1 ✓ |
两个坑：
- 弹栈条件必须是
<=。写成<会保留相等元素， 但相等时「\(a_i > a_j\)」不成立，答案会错。这题唯一的思维点就在这个等号上； - 异或和要增量维护，不能每次
reduce(xor, st)——那是 \(O(n^2)\)。 异或的自反性（\(x \oplus x = 0\)）保证了「弹出时异或一次」就等于「移除」， 见 03-运算符与位运算。
题解：solutions/BISHI121.py（已通过牛客判题机验证）
BISHI122 区间后缀极大位置计数（简单）¶
长度 \(n \le 10^6\) 的数组，对每个长度为 \(k\) 的子区间， 求其后缀极大值位置的个数。输出 \(n-k+1\) 行。 题面见 BISHI122 原题（牛客）。
BISHI121 是「前缀 + 单调栈」，这题是「滑动窗口 + 单调队列」。 由 BISHI121 的观察可知：答案就是单调递减队列在该窗口下的长度。
所以代码几乎和 sliding_max 一样，只是输出 len(q) 而不是 a[q[0]]。
\(n \le 10^6\) 且时限只有「其他语言 2 秒」，必须上性能写法：
list + 双指针（队列长度直接是 t - h + 1，连 len() 调用都省了）。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1])
a = list(map(int, data[2:2 + n]))
# 队列至多装 n 个下标，一次性开满，主循环里不再有扩容开销
q = [0] * n # 存下标
h = 0 # 队首（含）
t = -1 # 队尾（含）
res = []
push = res.append
for i in range(n):
x = a[i]
# 队尾弹出：值不超过 x 的旧下标不再是后缀极大位置（要求严格大于）；
# t >= h 同时充当判空，避免读到空队列的队尾
while t >= h and a[q[t]] <= x: # 相等也弹（严格大于）
t -= 1
t += 1
q[t] = i
# 队首下标 <= i-k 说明它已滑出窗口 [i-k+1, i] 的左端
if q[h] <= i - k:
h += 1
# 窗口凑满 k 个元素才输出；队内下标个数就是后缀极大位置的个数
if i >= k - 1:
push(t - h + 1) # ★ 答案就是队列长度
sys.stdout.write("\n".join(map(str, res)) + "\n")
main()
手动验证样例（n=5, k=3, a = 2 1 3 5 4）：
| \(i\)（0-indexed） | \(a_i\) | 队列（下标） | 窗口 | 输出 | 期望 |
|---|---|---|---|---|---|
| 0 | 2 | [0] |
— | ||
| 1 | 1 | [0,1] |
— | ||
| 2 | 3 | [2]（弹 1、0） |
\([0,2]\) | 1 | 1 ✓ |
| 3 | 5 | [3]（弹 2） |
\([1,3]\) | 1 | 1 ✓ |
| 4 | 4 | [3,4] |
\([2,4]\) | 2 | 2 ✓ |
Python 现实性评估：
| 项 | 量级 |
|---|---|
| 读入 \(10^6\) 个 token | read().split() 约 0.15 s |
map(int, ...) 建列表 |
约 0.25 s |
| 主循环 \(10^6\) 次迭代（含均摊的弹栈） | 约 1.0–1.5 s |
| 输出 \(10^6\) 行 | "\n".join 约 0.2 s |
时限「其他语言 2 秒」——这题在 Python 下是真的险。
能做的优化已经全部用上了：一次性读入、双指针代替 deque、
push = res.append 绑局部名、一次性输出。如果仍然 TLE，
只能说明这道题的数据规模对 Python 不友好，属于语言差而非做法错。
本题给出的判据：\(n = 10^6\) 且时限 2 秒的题，Python 大约只剩 「一遍 \(O(n)\) 的简单循环」的预算。任何每个元素多做几次 Python 层操作的写法 （
deque方法调用、函数封装、对象属性访问）都可能是压垮骆驼的稻草。
题解：solutions/BISHI122.py（已通过牛客判题机验证）
37.5 本章速查¶
| 要点 | 结论 |
|---|---|
| 核心思想 | 及时扔掉永远不可能成为答案的候选 |
| 复杂度 | \(O(n)\)，每个元素最多进出一次（均摊） |
| 单调栈求「更大」 | 用递减栈 |
| 单调栈求「更小」 | 用递增栈 |
| 求右边的 | 弹栈时给被弹元素赋答案 |
| 求左边的 | 弹完后看栈顶给当前元素赋答案 |
| 严格 vs 非严格 | 弹栈用 <= 得「严格更大」，用 < 得「大于等于」 |
| 哨兵技巧 | 两端加 \(\pm\infty\)，省掉判空和收尾 |
| 单调队列求最大 | 队列递减，队首是答案 |
| 单调队列求最小 | 队列递增 |
| 队首过期判断 | 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\) | 升级成斜率优化（凸壳） |
| 识别信号 → 想到什么 |
|---|
| 「左边/右边第一个比它大/小的」 |
| 「以每个元素为最值的最大区间」 |
| 直方图矩形、接雨水、最大全 1 子矩阵 |
| 「所有长度为 \(k\) 的窗口的最值」 |
| 「后缀最大值的集合」 |
| DP 转移是固定长度窗口的最值 |