单调栈图解：下一个更大元素，每个下标只进栈一次、出栈一次

问题是这样的：给一个数组，对每个位置，找它右边第一个比它大的数，没有就记 -1。LeetCode 496、503、739 都是它的变形，柱状图里的最大矩形（LeetCode 84）也建立在它之上。

直接写是两重循环：对每个 i，从 i+1 往右扫，遇到更大的就停。最坏情况是数组严格递减，每次都扫到底，比较次数 n(n-1)/2。单调栈把它降到 O(n)。这篇先画清楚栈里每一步装着什么，再解释为什么总操作数是线性的，最后说几个变形里最容易写反的地方。

单调栈的代码是一个 for 循环里套一个 while 循环，看起来像 O(n²)。它之所以是线性的，是因为每个下标最多进栈一次、出栈一次，while 循环在整个扫描过程中总共最多执行 n 次。下文先用一张逐步状态表展示栈里每一步的内容，再给出暴力解法和单调栈在 10 万个元素上的实测对比。

栈里放的是「还没找到答案的人」

从左往右扫。手里维护一个栈，里面放的是到目前为止还没找到右边更大值的下标。

新来一个元素 a[i]。栈顶那个下标对应的值如果比 a[i] 小，说明它等到了答案：右边第一个比它大的就是 a[i]。记下答案，弹出。继续看新的栈顶，直到栈顶不比 a[i] 小，或者栈空了。然后把 i 压进去，它也开始等。

这个过程自然让栈里的值从底到顶递减（严格来说是不增）。原因很直接：如果栈里某个值下面压着一个比它小的值，那个小的值在它入栈时就应该已经被弹出了。「单调」不是额外维护的性质，是弹栈规则的副产品。

逐步状态：2 7 3 5 4 6 1

下面是 Playground 程序对这个输入的实际输出，栈里显示的是值（程序内部存下标），从左到右是栈底到栈顶：

扫完以后，栈里剩下 7、6、1，它们右边没有更大的数，答案是 -1。最终答案：

下标:  0   1   2   3   4   5   6
值:    2   7   3   5   4   6   1
答案:  7  -1   5   6   6  -1  -1

i = 5 那一步最能说明问题。6 一来，先弹出 4（4 < 6），再弹出 5（5 < 6），遇到 7 停下。一次弹了两个，但这两个元素以后再也不会被看到。

为什么是 O(n)

看起来 for 里套了一个 while，像是 O(n²)。但换一个角度数：每个下标恰好被压栈一次；每个下标最多被弹出一次，弹出后永远不再回来。所以整个过程里 while 循环体执行的总次数，等于所有下标被弹出的次数之和，不超过 n。

程序里加了两个计数器。上面的输入 pushes=7 pops=4；换成 3 1 4 1 5 9 是 pushes=6 pops=5；全相等的 5 5 5 5 是 pushes=4 pops=0。无论什么输入，pops 都不会超过 pushes，而 pushes 恒等于 n。这种「单步可能很贵，但总量有上限」的分析叫摊还分析。

本机对比了暴力和单调栈，输入是严格递减数组（暴力的最坏情况），g++ 14.2 -O2：

clang++ 19.1 -O2 的耗时在同一量级（0.6 ms 对 1289 ms）。两种方法的答案逐个比对一致。n 放大 10 倍，单调栈约慢 10 倍，暴力约慢 100 倍。

在这里跑

程序读 n 和 n 个整数，输出每个位置的答案。不超过 16 个元素时打印每一步的栈；不超过 2000 个元素时，额外用暴力法逐个核对，对不上就报错退出。

g++ 14.2 与 clang++ 19.1 加 -O2 -Wall -Wextra 编译均无警告，默认 stdin 下两边输出完全相同：

i=0 a=2  stack=[2]  resolved: -
i=1 a=7  stack=[7]  resolved: 2
i=2 a=3  stack=[7 3]  resolved: -
i=3 a=5  stack=[7 5]  resolved: 3
i=4 a=4  stack=[7 5 4]  resolved: -
i=5 a=6  stack=[7 6]  resolved: 4 5
i=6 a=1  stack=[7 6 1]  resolved: -
answer: 7 -1 5 6 6 -1 -1
pushes=7 pops=4

stdin 写成 2 和 1，少一个数，stderr 输出 Expected 2 integers after the count.，退出码 1。

一个符号决定「更大」还是「不小于」

弹栈条件是 a[st.back()] < a[i]。把 < 改成 <=，含义就从「右边第一个严格更大的」变成「右边第一个大于等于的」。

用全相等的 5 5 5 5 试：< 版本一次都不弹，答案是 -1 -1 -1 -1；<= 版本每来一个 5 就把前一个弹掉，答案是 5 5 5 -1，pops=3。两者都对，看题目要哪一个。数组里有重复值时，题面上「更大」两个字要逐字核对。

求「下一个更小」，把比较方向反过来，栈就变成从底到顶递增。求「左边第一个更大」，可以从右往左扫，也可以照样从左往右扫，在压栈之前看一眼栈顶：弹完之后剩下的栈顶，就是左边第一个比 a[i] 大的。

几个变形

LeetCode 739 每日温度：要的不是更高的温度值，而是要等几天。弹出时记 i - st.back() 而不是 a[i]，所以栈里必须存下标。这也是上面的程序一开始就存下标的原因，存值会丢掉位置。

LeetCode 503 循环数组：数组首尾相接。把下标从 0 扫到 2n-1，用 i % n 取值，只在第一圈压栈。第二圈的作用是让第一圈剩在栈里的元素有机会遇到数组开头的那些数。

LeetCode 84 柱状图中最大的矩形：对每根柱子，找左右两边第一根比它矮的柱子，中间这段就是以它为高的最宽矩形。一次单调递增栈的扫描可以同时得到两个边界：某根柱子被弹出时，让它弹出的那根是右边界，它下面压着的那根是左边界。

滑动窗口最大值（LeetCode 239）：这时候要的是单调队列，不是单调栈。新元素从队尾进来，照样把比它小的都从队尾弹掉；区别在于队头的元素一旦滑出窗口，也要从队头移除。所以用 std::deque，两端都能出。每个下标仍然只进一次、出一次，整体还是线性。

和站上其他「单调」的区别

名字里都有单调，但不是同一件事。单调子序列构造图解 讲的是组合问题：怎样排一个序列，让最长上升和最长下降子序列都不超过 k。最长上升子序列里 lower_bound 必须严格 维护的是一个「各长度结尾最小值」的有序数组，靠二分更新，每步 O(log n)。单调栈只从栈顶进出，每步摊还 O(1)，回答的是「最近的那个更大或更小的数在哪」。

差分数组 常和它一起出现：单调栈先求出每个元素「管辖」的区间，比如它作为最大值的最长区间，然后用差分在这些区间上批量加值，最后一次前缀和还原。两步都是线性的。

LeetCode 901（股票价格跨度）是单调栈的在线版本：价格逐个到来，每来一个就要回答「往前连续多少天的价格不超过今天」。栈里保存（价格，跨度）二元组，新价格到来时把栈顶所有不超过它的元素弹出并累加跨度，再把自己压进去。每个价格仍然只进栈、出栈各一次，所以每次回答的摊还代价是 O(1)。