摊还分析 · 势能法

摊还代价的势能账本

单调栈的循环体里嵌着一个 while，看上去每个元素都可能触发 $O(n)$ 次弹出。这个担心不是多余的：把严格降序的数组后面接一个极大值，最后那一步确实要一口气弹掉前面所有元素。 $n = 100001$ 的这种输入上，实测单步最大代价就是 100001。

但整趟扫描的总代价仍是 $2n$ 量级。本页把这个结论从「每个元素进出各一次」这句口头论证，写成两种可验证的形式：聚合法给出的总量上界，与势能法给出的逐步账本。

1 · 聚合法的上界

聚合法只数总量，不管单步。入栈次数显然恰好是 $n$ ：循环体末尾无条件压入一个下标，一次不多一次不少。出栈次数不超过 $n$ ：每个下标至多被压入一次，因而至多被弹出一次。两者相加，总操作数不超过 $2n$ 。

实测的四组随机数组（值域 $10^6$ ）： $n = 100$ 时总操作 191（ $1.910n$ ）， $n = 1000$ 时 1989， $n = 10^4$ 时 19990， $n = 10^5$ 时 199989（ $2.000n$ ）。差额永远等于扫描结束时还留在栈里的元素数，这个量在随机输入上只有十几到二十几。

聚合法的局限也很明显：它给出总量，但对「某一步会不会特别贵」一个字都没说。而尾延迟只看那一步。

2 · 势函数与逐步账本

势能法把「便宜的操作预存信用、昂贵的操作花掉信用」这件事形式化。定义势函数 $\Phi_t$ 为第 $t$ 步结束后栈内的元素数，初值 $\Phi_0 = 0$ ；第 $t$ 步的摊还代价定义为 $\hat{c}_t = c_t + \Phi_t - \Phi_{t-1}$ ，其中 $c_t$ 是实际代价。

定理 2.1 取 $\Phi$ 为栈内元素数、 $c_t$ 为「一次入栈加本步的弹出次数」，则单调栈每一步的摊还代价恒为 $\hat{c}_t = 2$ ，与本步弹出多少个元素无关。

证明设第 $t$ 步弹出 $k_t$ 个元素。实际代价 $c_t = 1 + k_t$ 。栈的规模变化是「弹掉 $k_t$ 个、压入 1 个」，故 $\Phi_t - \Phi_{t-1} = 1 - k_t$ 。代入定义：

\hat{c}_t = (1 + k_t) + (1 - k_t) = 2

与 $k_t$ 无关。对 $t$ 求和并利用 $\Phi$ 的伸缩性质， $\sum_t c_t = \sum_t \hat{c}_t - \Phi_n + \Phi_0 = 2n - \Phi_n$ 。由 $0 \le \Phi_n \le n$ 得 $n \le \sum_t c_t \le 2n$ 。∎

这条恒等式是引擎测试里最锋利的一条断言：不是「摊还代价不超过某个常数」，而是每一步都精确等于 2。它在全部测试输入（含空数组、单元素、全相等、升降序与多组随机种子）乘以八个方向变体上逐项成立，任何一处代价记账写错都会当场红掉。

图 2-1 · 逐步的实际代价、势与摊还代价三条柱。可切换输入形状与弹栈判据，观察实际代价怎样起伏而摊还代价始终平在 2 上。

峰形输入把两者的差距推到极致。 $n = 100001$ 的「降序加尾峰」：单步最大实际代价 100001，总实际代价 200001，总摊还代价 200002，两者只差 1——那个 1 就是扫描结束时留在栈里的唯一元素。

3 · 栈深与内存占用

$\Phi$ 同时是空间的度量。栈深在实测里比想象中小：值域 $10^6$ 的随机数组用 nextGreater 判据扫过， $n$ 从 $10^2$ 涨到 $10^5$ ，最大栈深依次是 9、14、20、26，而同区间的 $\ln n$ 是 4.61、6.91、9.21、11.51。栈深与 $\ln n$ 同阶，常数在 2.2 到 2.3 之间。

原因是栈里存的是当前位置往左看的一段严格单调序列，也就是从右往左的「记录值」个数，随机排列下其期望正是调和数 $H_i \approx \ln i$ 。最坏情形仍是 $n$ ：严格降序输入的栈从头长到尾，一个都弹不掉。

图 3-1 · 最大栈深随 n 的变化，三条曲线分别是随机、降序与升序输入。可调 n 的上限，对照虚线的

\ln n

参考值。

注 · 那个 2.2 到 2.3 的常数没有找到出处。

四个测点（9 / 14 / 20 / 26）除以对应的 $\ln n$ 得到 1.95、2.03、2.17、2.26，看着像在缓慢上升而不是收敛到某个常数。这与「 $n$ 个位置上各自约 $\mathrm{Poisson}(\ln i)$ 的最大值」这一粗略模型相符：那样的最大值应当是 $\ln n$ 加一个 $\sqrt{\ln n}$ 量级的修正项，而不是 $\ln n$ 的常数倍。四个点分辨不开这两种模型，本页只报实测值，不给拟合式。

4 · 摊还与尾延迟的分野

摊还分析给的是总量保证，不是单步保证。这两个指标在单调栈上分得特别开：总操作数被钉死在 $2n$ ，而单步代价可以是 $n$ 本身。

对批处理这不构成问题——把一整个数组扫完的墙钟时间只看总量。对流式处理就不同了：若每个元素到达时都要在固定时限内给出答案，那么「某一个元素到达时要弹掉此前累积的十万个」就是一次超时，哪怕平均下来每个元素只花两次操作。

这条分野在别处也反复出现：动态数组的成倍扩容同样是摊还 $O(1)$ 、单次 $O(n)$ ，Redis 的 dict 为此专门做了渐进式 rehash 把一次大搬迁切成 $n$ 份。单调栈没有对应的补救办法，因为它的昂贵步骤不是可以推迟的维护工作，而是那一步真正要产出的答案：一口气弹掉的每个元素，各自的答案都在这一步才成立。要摊平它，只能改问题本身。

5 · 参考文献

Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2), 306–318.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed., §17.3 The potential method). MIT Press.
Rényi, A. (1962). Théorie des éléments saillants d'une suite d'observations. Colloquium on Combinatorial Methods in Probability Theory, 104–117. 随机序列中「记录值」个数的经典结果，即本页 §3 里栈深的期望。