单调栈

从左到右扫描，栈里保留尚未找到右侧更大元素的下标。若当前值 $a_i$ 大于栈顶值 $a_j$，就令 $\mathrm{next}(j)=i$ 并弹出 $j$；继续检查新的栈顶，直到栈空或栈顶值不小于 $a_i$，再压入 $i$。

因此从栈底到栈顶，下标严格递增，数值单调不增。相等的值可以同时留下，因为“相等”尚不足以回答“严格更大”。

最小实现 ​

from collections.abc import Sequence

def next_greater_indices(a: Sequence[int]) -> list[int]:
    """返回右侧第一个严格更大元素的下标；不存在时为 -1。"""
    answer = [-1] * len(a)
    stack: list[int] = []
    for i, value in enumerate(a):
        while stack and a[stack[-1]] < value:
            answer[stack.pop()] = i
        stack.append(i)
    return answer

assert next_greater_indices([2, 1, 4, 3, 3, 5]) == [2, 2, 5, 5, 5, -1]
assert next_greater_indices([2, 2]) == [-1, -1]
assert next_greater_indices([]) == []

代码使用 Python 3.9 及以上版本的类型标注；不修改输入。返回的是下标，取具体答案值前应先检查是否为 $-1$，否则 Python 的负下标会误读为最后一个元素。

六步跟踪 ​

对 $a=[2,1,4,3,3,5]$，表中栈写作“下标:值”，从左到右是栈底到栈顶。

两个值为 $3$ 的位置不会互相结算，直到遇到 $5$ 才一起得到答案。最后仍在栈里的位置，已经看过它右侧所有元素，答案就是 $-1$。

正确性与复杂度 ​

为什么找到的是“第一个” ​

假设 $j$ 在扫描到 $i$ 时被弹出。此时 $i>j$ 且 $a_i>a_j$，所以它是一个合法答案。若此前已经遇到某个 $j<k<i$ 满足 $a_k>a_j$，那么扫描 $k$ 时，所有压在 $j$ 上方的候选值都不大于 $a_j$；它们会先被 $a_k$ 弹出，随后 $j$ 也会被弹出，不可能一直留到 $i$。所以 $i$ 必是第一个合法位置。

这也解释了栈的单调方向：上方候选的值更小，当前值若足以解决下方候选，就必能先解决挡在上方的候选。单调性使需要处理的位置恰好连成栈顶的一段，而无需在栈中间搜索。

为什么嵌套循环仍是线性 ​

每个下标恰好压栈一次，弹出后不再回来，因此全部扫描期间最多发生 $n$ 次压栈和 $n$ 次弹栈。内层循环的成功执行总计至多 $n$ 次；每个外层步骤再承担至多一次结束循环的检查。

在数组访问、值比较为常数成本的模型下，总时间 $O(n)$，额外空间 $O(n)$。某一步仍可能弹出几乎整个栈，所以这是摊还线性理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。，不是每一步最坏都只做常数工作。Python 的列表尾部追加本身也采用摊还成本分析。

下图展示后文的另一种用法：为当前元素寻找左侧最近更小值。它使用递增候选栈，与上面的右侧严格更大任务采用不同的弹栈理由。

相等元素决定比较符号 ​

在同一个左到右、为被弹元素填写右侧答案的模板中：

例如 [2,2,3] 的严格更大下标为 [2,2,-1]，大于等于下标却为 [1,2,-1]。四个比较符号只适用于这里固定的扫描和填答案方式，不能脱离模板死记。

求“当前元素左侧最近的严格更小元素”时，常见做法是先弹出值大于等于当前值的候选，再读剩余栈顶作为当前元素的答案。此时弹出理由变了：旧候选位置更远、值又不小于新元素，以后只要旧候选够小，新元素也够小且更近，所以旧候选被永久支配；并不是说当前值替它找到了右侧答案。

柱状图与并列归属 ​

对于高度 $h_j$，如果左右第一个严格更矮的位置分别为 $L_j,R_j$，那么以这根柱高为矩形高度，可以覆盖区间 $(L_j,R_j)$，面积为 $h_j(R_j-L_j-1)$。没有更矮柱的一侧用边界 $-1$ 或 $n$。例如 [2,1,5,6,2,3] 中，高度 $5$ 的左右障碍位于下标 $1,4$，面积为 $5\times 2=10$。

所有最优矩形都能选到一根达到其最小高度的柱，因此比较各柱的最大合法跨度足够。若算法改为统计子数组最小值的贡献，同一段中的相等最小值却不能重复认领；常用“一侧严格、另一侧非严格”的边界分工，为每个子数组指定唯一归属。求最大值与计数对重复结算的容忍度不同。

单调栈适合最近更大/更小元素、股票跨度和柱状图等静态邻近问题；它的本质是用顺序与值的关系，证明某些候选可以永久消失。并不是只要一个问题出现“最大值”就适合使用。

SMAWK理路SMAWK 全单调矩阵搜索SMAWK algorithm交替执行列淘汰、奇数行递归与有界插值，在线性求值次数内找出全单调矩阵的每行最左极小值。也用候选栈，但淘汰的是矩阵整列：一个列在上方行已经失去资格，又在当前行被新列严格击败，才能由全单调性理路全单调矩阵与行极小值Totally monotone matrix把行极小列的单调性要求推广到所有保序子矩阵，用严格二乘二比较刻画可安全删行删列的结构。推出下方行也不需要它。这里复用的是栈的操作结构，不能直接借用一维最近更大元素的证明。

采用一致的并列规则后，相同的弹栈结构还能在线性时间构造笛卡尔树理路笛卡尔树Cartesian tree同时满足下标中序与数组值堆序的唯一二叉树。，并进一步把静态 RMQ理路静态区间最值查询（RMQ）Range minimum query · RMQ预处理静态数组后，返回区间最小元素的位置并固定并列规则。 与树上祖先问题联系起来。但单调栈本身不直接回答任意区间查询，也不在数组更新后自动恢复已经删除的候选。数据能否改变、答案是当前结算还是未来候选，必须随问题重新检查。

元素的比较依赖全序理路全序Total order · Linear order任意两个元素都可比较的偏序。；相等元素的处理则由所求边界采用严格还是非严格不等式决定。