栈、单调栈与单调队列 · HTML
数学 / 逻辑形态
扫描 i；当 a[i] 满足 resolve(a[stack[-1]],a[i]) 时弹出 j 并确定其右边界 i。随后压入 i；栈中值保持所选单调方向。
识别信号
- 要求每个位置左/右第一个更大或更小。
- 候选一旦遇到支配元素便可永久确定答案。
- 需要每元素作为最小/最大值的影响区间。
- 朴素向左右扫描是 O(n²)，但未解决候选可有序压缩。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 任意范围最大值查询 | 单调栈解决最近边界，不直接回答任意在线区间极值。 |
| 滑动窗口极值 | 候选还会因过期离窗，需双端可删的 monotonic-deque。 |
核心不变量
栈中索引递增，值按指定方向单调；栈内每个索引都尚未遇到能解决它的右侧元素。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 索引栈、当前 i/value、比较严格性（> 或 ≥）与答案数组。 |
| Transition | 新值反复弹出被其解决的栈顶并写答案；停止时压入当前索引。 |
| Frontier / order | 所有尚无右侧答案的非支配候选；被弹元素永不再有价值。 |
Python 骨架
def next_strictly_greater(values):
answer = [-1] * len(values)
stack = [] # indexes, values strictly decreasing
for i, value in enumerate(values):
while stack and values[stack[-1]] < value:
j = stack.pop()
answer[j] = i
stack.append(i)
return answer
正确性思路
- 弹出 j 时当前值比 a[j] 大，且 j 在栈期间所有中间扫描值都未能弹出它，因此 i 是第一个严格更大位置。
- 未弹候选按值单调保留，任何被新值支配的候选都已全部解决。
- 每个索引入栈一次、出栈至多一次；结束未弹者确实没有右侧更大值。
复杂度
| Time | Space | Parameters |
|---|
| O(n) | O(n) | 虽然有嵌套 while，但每个索引全程只 push/pop 各一次，摊还线性。 |
边界条件
- 空数组返回空答案。
- 严格与非严格比较会改变重复值归属。
- 单调递减输入可能让栈增长到 n。
- 需要左边界时可反向扫描或在入栈前读取栈顶。
错误模式
| Pattern | Why it fails / fix |
|---|
| 栈存值却需要索引 | 距离、边界与重复值通常要求存索引。 |
| < 与 <= 随意替换 | 重复值会被双计或漏计，必须由严格性定义决定。 |
| 误判嵌套循环 O(n²) | 用每索引至多弹一次做摊还分析。 |
选择与排除规则
- 关键词 first/nearest greater/smaller：单调栈。
- 窗口过期也要移除候选：单调队列。
- 贡献计数先确定每个元素左右支配边界，再计算覆盖组合。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 答案索引为 [3,2,3,-1]。 |
| Setup | 值 [5,2,4,7]，求右侧首个严格更大索引。 |
| Trace | 4 弹出 2 的索引；7 再弹 4 与 5 的索引。 |
Recall prompts
我的补充