被弹掉的元素为什么不用再回头：单调栈的均摊 O(n) 从哪来
单调栈是一个始终保持栈内元素按值单调的栈，用来回答"每个元素左/右第一个比它大或小的元素在哪"。它把两两比较的 O(n²) 压到 O(n)，靠的不是运气，而是"元素一旦被弹出，答案就永久确定"这条不变量：每个下标最多进栈一次、出栈一次，总操作数是 2n。最常见的误区是把嵌套 while 当成 O(n²)、只往栈里存值而不存下标，以及忽略"严格大于"和"大于等于"在重复元素上的差别。读完你能写对模板、说清均摊证明，并知道环形数组、每日温度、柱状图最大矩形各自该怎么改。
是什么
单调栈是一种在普通栈上额外维持一条规则的栈：从栈底到栈顶，元素对应的值始终单调递增或单调递减。它最典型的用途是回答"下一个更大元素"这类问题——对数组中每个位置，找出它右边第一个比它大的数，找不到就记为 -1。
一句话直觉：栈里放的不是"处理过的元素"，而是"还没等到答案的候选人"。一旦来了一个更大的数，所有比它小的候选人会在同一时刻拿到答案，于是可以集体离开，永远不必再被检查。
常见场景包括每日温度（还要等几天才升温）、股票跨度（连续多少天价格不高于今天）、柱状图中的最大矩形、接雨水，以及"删掉 k 位数字使剩下的数最小"。它们的共同点是：每个位置关心的不是全局最值，而是它右侧第一个越过某个阈值的邻居。
核心原理
先看最朴素的写法：对每个 i 向右扫描，直到遇到第一个更大的数。最坏情况下数组严格递减，每个位置都要扫到底，复杂度 O(n²)。单调栈要做的，是把"已经能确定答案"的比较提前结算掉。
维护一条不变量：栈中存放的是尚未找到答案的下标，它们对应的值从栈底到栈顶严格递减。扫描到新元素 x 时，只要栈顶的值比 x 小，栈顶的答案就是 x——因为如果它和 x 之间还存在更大的数，那个数在扫过时早就把它弹走了。弹出并写答案，重复到栈顶不小于 x，再把当前下标压栈。
def next_greater(nums):
n = len(nums)
ans = [-1] * n
stack = [] # 存下标，值从栈底到栈顶递减
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
ans[stack.pop()] = x # 弹出即结算，答案永久确定
stack.append(i)
return ans这个模板里，每个下标恰好被压栈一次，也最多被弹出一次，所以 while 循环体的总执行次数不超过 n。外层循环 n 次，总操作数约 2n，均摊到每次扫描是 O(1)，整体 O(n)，额外空间 O(n)。注意"均摊"二字的含义：单次操作仍可能很贵——一个严格递减的数组在最后遇到最大值时，会一次性弹空整个栈；但把整趟扫描合起来看，总代价被前面的"只压不弹"摊平了。
有一个很好用的类比：银行柜台前排队的人手里拿着号码，柜台叫号时只叫"当前窗口能办的最大号码"。更贴切的是看楼：从左往右走，栈里记着一串"还没看到更高楼层"的楼；当一栋更高的楼出现，所有比它矮的楼同时确定了"右边第一栋更高的楼就是它"，之后再出现多高的楼都与这些矮楼无关。
如果从右往左扫描，模板会变成"栈顶就是答案"：保持栈内值单调递减（从栈底到栈顶），遇到当前元素时先把所有不大于它的栈顶弹掉，此时栈顶就是右边第一个更大的数，然后再压入自己。两种方向都能求"右侧第一个更大"，区别在于从左往右是"来了新数才结算旧的"，从右往左是"轮到自己时从栈里取现成答案"。求"左侧第一个更大"时，把扫描方向反过来即可。
常见考点与误区
- 误区一：看到嵌套 while 就判 O(n²)。 面试里最常见的追问是"你这两层循环凭什么说线性"。要答出势能/记账式的均摊论证：元素只进栈一次，出栈次数以进栈次数为上限，while 的总迭代次数不超过 n，而不是每轮都可能跑 n 次。
- 误区二：栈里存值而不是下标。 存值只能回答"更大的数是多少"，回答不了"在哪个位置"和"隔了几天"。每日温度要写
i - stack[-1]，下一个更大元素 II 要按i % n落位，柱状图要算宽度，全都依赖下标。遇到重复值时，光凭值也无法区分是哪一个。 - 考点三：严格大于还是大于等于。 弹栈条件写
<还是<=，决定了答案是"右边第一个严格更大"还是"第一个不小于它的"。对[2, 2, 3]，前者第二个 2 的答案是 3，后者是第一个 2。题目没说清时先问语义，再把比较符写进注释。 - 考点四：环形数组直接扫两圈。 下一个更大元素 II 的常见错法是遍历
2n并把答案写两遍，后一遍会把前一遍的正确结果覆盖成自己或更远的值。正确做法是遍历2n - 1次、用i % n取元素，且只在i < n时写入答案；同时栈里存的下标也要取模或允许重复，否则距离计算会错位。 - 考点五：以为所有"下一个更大"变体都能一趟出答案。 柱状图最大矩形需要知道左右两侧第一个更矮的柱子，通常要两次单调栈或一次带哨兵的扫描；接雨水的单调栈版本是按"行"累加水量，和双指针按列算是两套思路。模板能复用，边界条件不能照抄。
- 考点六：忘记栈里剩下的元素。 扫描结束后仍在栈中的下标就是"右边没有更大元素"的位置，答案保持初始化的 -1。初始化写成 0 或 n 会在最后暴露成错误答案。
实践建议
- 把不变量写在代码上面。 "栈内存下标，值从栈底到栈顶递减，栈内元素尚未结算"这三句注释，比记住模板更能防止在变体里写错方向。面试时也建议先口述不变量，再写循环。
- 用哨兵省掉收尾，但要想清值域。 在数组末尾追加一个正无穷大，可以保证所有元素最终被弹出，省去扫描结束后的清理；代价是哨兵必须严格大于所有合法值，且不能影响下标计算。值域不确定时宁可老实保留收尾逻辑。
- 重复元素的语义先定死。 统一用
<或统一用<=，并在函数名或注释里体现，例如next_strictly_greater。涉及去重、区间合并的题，弹不弹等值元素会直接改变结果。 - 环形与流式场景分开处理。 环形数组用
2n - 1次取模遍历；而监控指标里的"连续多少天新高"是流式的，只能保留栈，最坏空间 O(n)（长期递减序列），不要假设内存是常数。 - 自测四类边界。 单元素、严格递增、严格递减、全部相等，这四组能覆盖空栈、连续弹空、收尾残留和等值判断四种情况。写完先手动跑一遍栈的变化，比盯着代码找 bug 快。
一句话总结：单调栈的线性来自"弹出即定案"，每个元素只进出一次，均摊掉看似昂贵的 while。