第 37 章 单调栈¶
单调栈只做一件事：及时扔掉那些已经被证明永远不可能成为答案的候选。 栈里始终保持单调，每个元素最多进出一次，于是一大批 \(O(n^2)\) 的「向左/向右找第一个 比它大/小的元素」被压到 \(O(n)\)，实现只有几行。
「左右第一个更大/更小」「以每个元素为最值的最大区间」「直方图最大矩形」「接雨水」 都是同一个模型的变体。把这套思想搬到滑动窗口上就是 单调队列——那是它的另一种形态。
1 它解决什么问题¶
给定长为 \(n\) 的序列，求每个元素右边第一个比它小的元素。没有则输出 0。 \(n \le 10^6\)。
暴力是 \(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)\) 是同一类论证（序列与数组）。
2 四种方向的对照表¶
这是最容易记混的地方。记住两条规则：
- 求「更大」用递减栈，求「更小」用递增栈（栈的单调性和目标相反）；
- 求右边就正序扫，求左边就倒序扫。
| 目标 | 扫描方向 | 栈的单调性 | 弹栈条件（a[st[-1]] vs a[i]） |
|---|---|---|---|
| 右边第一个更大 | 正序 | 递减 | <= a[i] 弹 |
| 右边第一个更小 | 正序 | 递增 | >= a[i] 弹 |
| 左边第一个更大 | 倒序 | 递减 | <= a[i] 弹 |
| 左边第一个更小 | 倒序 | 递增 | >= a[i] 弹 |
严格 vs 非严格：弹栈条件用
<=还是<，决定了「相等元素」怎么处理。 - 用<=（弹掉相等的）：得到的是「第一个严格更大的」； - 用<（保留相等的）：得到的是「第一个大于等于的」。有重复元素的题目一定要想清楚这一位，这是单调栈最常见的 WA 来源。
3 模板¶
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：弹完之后看栈顶给当前元素赋答案（「谁挡在前面」）。求「右边的」用前者，求「左边的」用后者，都只需要正序扫一遍， 不需要真的倒着扫。这比上面那张表更实用。
4 经典应用：直方图中最大矩形¶
给定柱状图，求其中面积最大的子矩形。
思路：
以每个柱子做高，向左和向右分别找出第一个比它矮的柱子， 这个是能覆盖的极大子矩形。可以使用正反两次单调栈扫描完成。
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 子矩阵、接雨水、柱状图问题， 都是「向左右找第一个不满足条件的位置」。
5 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI121 | 数列后缀极大位置统计 | 简单 | 题解 |
| BISHI122 | 区间后缀极大位置计数 | 简单 | 题解 |
| BM94 | 接雨水问题 | 较难 | 题解 |
| LC42 | 接雨水 | 困难 | 题解 |
| LC84 | 柱状图中最大的矩形 | 困难 | 题解 |
| LC739 | 每日温度 | 中等 | 题解 |
BISHI121 数列后缀极大位置统计（简单）¶
数列 \(a\) 初始为空，\(n \le 10^5\) 次操作每次在末尾添加正整数 \(x\)。 每次操作后，求当前所有后缀最大值下标（下标从 1 开始）的按位异或和。 下标 \(i\) 是后缀最大值下标当且仅当对所有 \(i < j \le |a|\) 都有 \(a_i > a_j\)（严格）。 题面见 原题。
核心观察：「后缀最大值下标的集合」就是单调递减栈本身。
为什么？栈中保持严格递减，意味着栈里每个元素都严格大于它右边所有还在栈里的元素； 而被弹出的元素恰恰是「存在右边某个元素 \(\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\)）保证了「弹出时异或一次」就等于「移除」， 见 运算符与位运算。
BISHI122 区间后缀极大位置计数（简单）¶
长度 \(n \le 10^6\) 的数组，对每个长度为 \(k\) 的子区间， 求其后缀极大值位置的个数。输出 \(n-k+1\) 行。 题面见 原题。
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/nowcoder/BISHI122/sol.py（已通过判题机验证）
BM94 接雨水问题¶
给定长度 \(n\) 的高度数组，求柱子之间能接住多少水。 它是 §4「直方图中最大矩形」的近亲：同样是「向左右各找第一个比自己高的柱子」， 只是求的东西从面积换成了水量。
按单调栈做的写法是维护一个递减栈：遇到比栈顶高的柱子就说明找到了右边界， 弹出栈顶当「凹底」，此时新的栈顶就是左边界， 这一层的水量是 \((\min(h_{左}, h_{右}) - h_{凹底}) \times (右 - 左 - 1)\)。 按层横向累加是单调栈解法的特点，与下面那种按列纵向累加的解法算出来是同一个数。
这题另有两条不用栈的路，都值得知道：
| 解法 | 思路 | 复杂度 | 额外空间 |
|---|---|---|---|
| 单调栈 | 横向按层累加 | \(O(n)\) | \(O(n)\) |
| 预处理前后缀最大值 | 第 \(i\) 列的水量是 \(\min(\max_{\le i}, \max_{\ge i}) - h_i\) | \(O(n)\) | \(O(n)\) |
| 相向双指针 | 哪边的前缀最大值小就先结算哪边 | \(O(n)\) | \(O(1)\) |
三条路同阶，差别在额外空间与思维负担。 前缀最大值那条最容易写对，双指针那条最省空间，见 双指针与滑动窗口。
另一处题库里的三道单调栈题¶
LC 739. 每日温度 是模板的原样应用：求每个位置右侧第一个更大元素的下标距离， 维护一个自栈底向栈顶递减的下标栈，遇到更大值就连续弹栈并当场结算。 对照那张四种方向的表，它落在「向右找第一个更大」那一格。
LC 84. 柱状图中最大的矩形 与本章「直方图中最大矩形」是同一道题： 每根柱子向左右各找第一个比它矮的柱子，宽度由这两个边界确定，一遍单调栈 \(O(n)\)。 两侧加哨兵（左端补 \(-1\)、右端补一根高度为 \(0\) 的柱）能省掉「栈空」与「扫尾」两处特判。
LC 42. 接雨水 与接雨水问题是同一道题，上面已按单调栈的口径讲过一遍。 值得对照的是它的双指针解法：左右各维护一个前缀最大值， 每次移动较矮的那一侧，该侧当前列的储水量当场结算，\(O(n)\) 时间、\(O(1)\) 空间。 单调栈是按层横着结算，双指针是按列竖着结算，两条路加出来的是同一个总量。
6 本章速查¶
| 要点 | 结论 |
|---|---|
| 核心思想 | 及时扔掉永远不可能成为答案的候选 |
| 复杂度 | \(O(n)\)，每个元素最多进出一次（均摊） |
| 求「更大」 | 用递减栈 |
| 求「更小」 | 用递增栈 |
| 求右边的 | 弹栈时给被弹元素赋答案 |
| 求左边的 | 弹完后看栈顶给当前元素赋答案 |
| 严格 vs 非严格 | 弹栈用 <= 得「严格更大」，用 < 得「大于等于」 |
| 哨兵技巧 | 两端加 \(\pm\infty\)，省掉判空和收尾 |
| 识别信号 → 想到什么 |
|---|
| 「左边/右边第一个比它大/小的」 |
| 「以每个元素为最值的最大区间」 |
| 直方图矩形、接雨水、最大全 1 子矩阵 |
| 「后缀最大值的集合」 |
窗口相关的信号（固定长度窗口最值、DP 转移是窗口最值）见 单调队列 章末。