单调栈
01 / 一句话本质
维护一个值保持单调的栈 —— 每当下一个元素将打破顺序时,你弹出的恰好是那些 "当前元素就是其答案" 的元素。
题目每个下标的下一个更大元素输入[2, 1, 2, 4, 3, 1]
输入
20
11
22
43
34
15
栈 →
— 空 —
结果
?0
?1
?2
?3
?4
?5
从左到右扫描。维护一个下标栈,使得栈中对应的值从栈底到栈顶严格递减。
步
0 / 16
i
—
栈大小
0
结果已填
0 / 6
0 / 16
02 / 模式骨架
# 下一个更大元素 —— 严格递减栈stack ← [ ]for i in 0..n−1:while stack 非空 且 arr[stack.top] < arr[i]:j ← stack.pop()result[j] ← arr[i] // i 即为 j 的下一个更大元素stack.push(i)# 栈中剩下的元素右侧无更大者 → result ← −1
03 / 什么时候用这个模式
"下一个更大 / 更小"
对每个元素,需要它右侧(或左侧)最近的更大(或更小)元素。 这个模式在违反者出现的那一刻,正好给出对应下标的答案。
"对每个,找..."
答案是逐下标的,而非汇总值 —— 而且关系是位置上的,不是基于数值的。
"柱状图 / span"
最大矩形、接雨水、股票跨度 —— 这些问题的边界都由最近的更大 / 更小邻居确定。
"O(n)"
目标复杂度排除了 O(N²) 的逐下标扫描,暗示要做摊销的单趟扫描。
04 / 常见坑
i.
存值而不是下标。
弹出时几乎总要写入
result[j] —— 因此栈必须记住每个弹出元素的来源位置。 存下标,值通过 arr[stack.top] 查表得到。ii.
内层 while 中的
< 与 ≤。严格(
<)是"下一个严格更大" —— 相等元素会在栈中等待,直到出现更大的值。 非严格(≤)是"下一个不小于" —— 相等者也会被弹出, 互为答案。这是两个不同的问题;选择会在相等情形悄无声息地改变结果。iii.
忘了处理末尾的剩余项。
循环结束时仍留在栈中的下标,其右侧没有下一个更大元素。 把它们的结果初始化为
-1(或按规约跳过)。这是最容易漏掉的地方。05 / 去 LeetCode 上练习
四道题,按难度排序。前两道是 next-greater 的热身;后两道才真正展现单调栈不可或缺的一面。