monotonic stack · next greater

monotonic stack 的形状

一排柱子，问每根柱子往右第一根比它高的在哪。朴素写法对每根柱子各扫一遍右侧，最坏要比较 $n(n-1)/2$ 次。monotonic stack 用一个额外的栈把这件事压成一遍扫描：栈里存下标，对应的值保持单调；每个新元素进来之前，先把栈里所有「不如自己」的弹掉。

关键不在栈本身，而在弹出的那一刻。被弹出的元素，正好是那些「还没找到答案、而新元素就是它们的答案」的元素。答案在此刻确定，之后再也不必回头看它。本页把这句话拆开，本系列其余各页都是它的推论。

1 · 朴素解法的代价

朴素解法的形状很直白：对每个 $i$ ，从 $i+1$ 往右走，遇到第一个 $a[j] > a[i]$ 就停。最坏情形是严格递减的数组，每个 $i$ 都要走到末尾，总比较次数 $n(n-1)/2$ 。

值得先量一量这个「最坏」离日常有多远。 $n = 20000$ 时，五种输入形状下朴素扫描的实测比较次数是：值域 $10^6$ 的随机数组 $8.91n$ 、值域 4 的随机数组 $2510n$ 、全相等数组 $9999.5n$ 、严格降序 $9999.5n$ 、严格升序 $1.00n$ 。

图 1-1 · 朴素外扫与 monotonic stack 的比较次数对照，五列分别是随机、重复、全等、降序、升序五种输入形状。可调长度与值域，观察重复元素怎样把朴素解法推向平方级。

第一列那个数字推翻了本页最初的写法。原稿写的是「朴素解法在随机数据上就已经慢一个量级」，实测不成立：值域够宽的随机数组里，「下一个更大元素」通常就在近处，总比较次数实测约 $n \ln n$ —— $n$ 从 1000 涨到 400000，系数从 $7.31$ 涨到 $13.94$ ，同区间的 $\ln n$ 从 $6.91$ 涨到 $12.90$ 。两者贴得很近。真正逼出平方级的是重复元素与有序输入：值域压到 4，系数就跳到 $2510$ ；全相等数组则精确落在 $9999.5n = n(n-1)/2$ 上。

这一点决定了后面几页的取材口径：凡是要展示「单调栈比朴素快」的地方，输入必须含大量重复元素，否则量出来的差距会小得看不出结论。

2 · 栈内单调性的来源

设弹栈判据是「栈顶值小于当前值就弹」。处理 $i$ 时把满足这个条件的栈顶一路弹掉，剩下的栈顶必然不小于 $a[i]$ ，然后把 $i$ 压上去。归纳一步即得：栈从底到顶，值单调不增。

单调性不是目的，而是「不必回头」的保证。栈里之所以只留下不小于 $a[i]$ 的元素，是因为比 $a[i]$ 小的那些已经拿到了答案：它们要找的是右侧第一个更大的值，而 $a[i]$ 就在它们右边、且比它们大。已经结清的元素退场，栈里永远只剩「悬而未决」的那些。

图 2-1 · monotonic stack 的逐步扫描。深色柱是当前元素，红色柱是本步被弹出的，绿色柱是答案已定的。可切换弹栈判据、换输入数组，并单步观察每一步定下了谁的答案。

代价的账很好算。每个下标恰好入栈一次；出栈至多一次，因为一旦被弹出就不再回来。总操作数不超过 $2n$ ，与单步的 while 循环跑多少圈无关。实测值域 $10^6$ 的随机数组， $n = 10^5$ 时入栈 100000 次、出栈 99989 次，合计 $2.000n$ ；单步最大代价 20 次弹出，最大栈深 26。摊还的完整论证见摊还代价的势能账本。

3 · 一遍扫描的两组答案

同一遍扫描产出的是两组独立的答案，而多数教程把它们拆成了两次遍历。

被弹出者拿到的是 next 方向的答案：把 $i$ 弹出去的那个下标，就是 $i$ 右侧第一个「更大」的位置。而新元素入栈时压在它下面的那个栈顶，是 prev 方向的答案： $i$ 左侧第一个「不小于」它的位置。

弹栈判据 $a[\text{top}] < a[i]$ 一遍扫完：读「谁弹了我」得 nextGreater，读「我压在谁上面」得 prevGreaterEq

严格性在两侧换了位置：同一条判据，next 侧给出的是严格更大，prev 侧给出的却是不小于。这不是巧合：判据 $<$ 的否命题是 $\ge$ ，弹不掉的那个正好满足 $\ge$ 。八个方向变体（next 与 prev 各四种，严格与非严格成对）因此只需要四条判据。这个错位是管辖区间与贡献法那一页整个坑的来源。

4 · 方向变体与弹栈判据

四条判据与它们的两个副产品：

弹栈判据	读 next 得到	读 prev 得到
$a[\text{top}] < a[i]$	nextGreater（严格）	prevGreaterEq（不小于）
$a[\text{top}] \le a[i]$	nextGreaterEq（不小于）	prevGreater（严格）
$a[\text{top}] > a[i]$	nextSmaller（严格）	prevSmallerEq（不大于）
$a[\text{top}] \ge a[i]$	nextSmallerEq（不大于）	prevSmaller（严格）

越界的约定要一并定下来，否则贡献法的宽度会算错：next 方向找不到就记 $n$ ，prev 方向找不到就记 $-1$ 。这样「管辖宽度」永远等于 $\text{right} - \text{left} - 1$ ，不需要为边界单独分支。

图 4-1 · 八个方向变体在同一数组上的答案对照，严格与非严格分岔的位置被单独标出。可换数组并把值域压到 2 观察相等元素处的差异。

全相等数组是检验这张表最省事的输入。长度 10 的全等数组上，四个严格变体的答案一律越界（nextGreater 与 nextSmaller 全是 10，prevGreater 与 prevSmaller 全是 $-1$ ），四个非严格变体一律指向紧邻位（nextGreaterEq 是 $1, 2, \dots, 10$ ，prevSmallerEq 是 $-1, 0, \dots, 8$ ）。无重复元素时八个变体两两合并成四组，看不出区别。

警示 · 逐步轨迹的内存是平方级的。

本系列的引擎给每一步存一份栈快照，供 lab 单步回放。降序输入下每一步的栈都是满的，快照总格子数恰好 $n(n+1)/2$ ：实测 $n = 2000$ 时 200 万格、堆增量 16.4 MB； $n = 8000$ 时 3200 万格、234 MB； $n = 20000$ 时 2 亿格、1514 MB，再往上直接把 node 的默认堆撑爆。

引擎因此把轨迹做成了开关：只要答案的调用路径（monoIndex 及其全部下游）一律不建轨迹，只有 lab 的几十个元素才开。这个坑是在写测试时撞上的——一条「 $n = 10^5$ 的降序输入」的性能断言让整个 vitest 进程 OOM 退出，而算法本身是严格线性的。

5 · 参考文献

Berkman, O., Schieber, B., & Vishkin, U. (1993). Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. Journal of Algorithms, 14(3), 344–370.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed., §17.1–17.3). MIT Press.
Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1 (3rd ed., §2.2.1). Addison-Wesley.
All nearest smaller values. Wikipedia. 该问题的标准命名与并行算法综述。