接雨水 · 股票跨度 · 删数 · median

一整类问题的落地

前几页的结构已经完整。本页把它能解的题排开，重点不在题目本身，而在「什么时候该换别的结构」。四道题里前三道走单调栈，第四道走两个堆，而第四道恰恰说明了单调栈的边界在哪。

1 · 接雨水与按层结算

一排宽度为 1 的柱子，求下雨后能积多少水。位置 $i$ 上的水深是 $\min(\text{左侧最高}, \text{右侧最高}) - h[i]$ ，负则记 0。

单调栈的读法与其他题不同：它不是按列竖着算，而是按层横着算。维护一个高度递减的栈，遇到比栈顶高的柱子就弹栈，弹出的那根柱子是「凹槽的底」，它左边的新栈顶是左墙，当前柱子是右墙，这一层的水量是 $(\min(\text{左墙}, \text{右墙}) - \text{底}) \times (\text{右墙下标} - \text{左墙下标} - 1)$ 。

以 $h = [0,1,0,2,1,0,1,3,2,1,2,1]$ 为例，四次结算分别发生在 $i = 3$ （得 1）、 $i = 6$ （得 1）、 $i = 7$ （得 3）、 $i = 10$ （得 1），合计 6。

图 1-1 · 接雨水的单调栈解法与对撞双指针解法并排。左侧按层横向结算，右侧按列竖向结算。可编辑柱高并单步观察两者的结算顺序差异。

对撞双指针的思路完全不同：左右各一个指针往中间走，谁矮就结算谁并内移。这条解法的空间是 $O(1)$ ，比单调栈的 $O(n)$ 更省，而且不需要栈这个概念。接雨水那一页从双指针一侧完整讲了它成立的理由。

两条解法的真正分野在可推广性。双指针依赖「水面高度由两侧最高值的较小者决定」这一条特有性质，换一道题就未必成立；单调栈依赖的是「每个元素的左右第一个更大者」，那是一条通用的结构性质。求柱状图最大矩形时双指针无从下手，而单调栈的代码几乎一样。

2 · 股票跨度

给一串每日价格，求每天的「跨度」：从今天往前数，连续有多少天的价格不高于今天。这是 prevGreater 的直接读法：设 $P$ 是今天左侧第一个严格更高的日子，跨度就是 $i - P$ 。

$[100, 80, 60, 70, 60, 75, 85]$ 的跨度是 $[1, 1, 1, 2, 1, 4, 6]$ 。最后一天价格 85，往前数到第 0 天的 100 才被挡住，跨度 6。

图 2-1 · 股票跨度的逐日计算。绿色横条是当日跨度覆盖的天数，栈里留着的是历次「还没被超过」的高价日。可编辑价格序列并单步推进。

这道题值得单列，是因为它是单调栈少见的在线形态：价格一天一天到来，每天要立刻给出答案，不能等全部数据到齐。单调栈天然支持这一点，因为 prevGreater 的答案在元素入栈时就已确定，不依赖任何未来的数据。反过来，nextGreater 那一族做不到在线，被弹出者的答案要等到弹它的那个元素出现。

3 · 字典序最小的删数

给一个十进制数字串，删掉 $k$ 位使剩下的数最小。贪心的直觉是：从左往右扫，只要当前位比前一位小，就把前一位删掉，因为高位小一档比低位小多少都值。

落到实现上就是一个保持不减的栈加一份删除预算：新字符比栈顶小、且预算还有剩，就弹掉栈顶并扣一次预算。扫完若预算没用光，从尾部继续删；此时栈内已是不减序列，删尾部就是删最大的那些位。最后剥掉前导零，全空则输出 0。

四组结果：removeKDigits("1432219", 3) 得 1219，("10200", 1) 得 200，("541270936", 3) 得 120936，("112", 1) 得 11。

图 3-1 · 删 k 位得最小的逐字符过程。绿色是留下的位，红色是被弹掉的位。可改数字串与 k，并对照穷举全部保留子序列的结果。

注 · 前导零与空串这两个边界，是被穷举 oracle 逼着定死的。

("10200", 1) 的栈结果是 0200，剥掉前导零得 200；("10", 2) 的栈结果是空串，约定输出 0。这两条约定本身不难，麻烦在于测试里的穷举参考实现必须用同一套约定：它枚举全部保留子序列后取最小，若拿字符串字典序比较，"0200" 会小于 "200"，两边就永远对不上。参考实现最终改成按 Number() 比数值、且同样做剥零处理，两边才在八组用例乘以全部 $k$ 上逐项相等。

4 · 滑动窗口 median 与对顶堆

把「窗口最大值」换成「窗口 median」，单调队列立刻失效。原因很直接：单调队列能扔掉的只是「永远当不上最大值」的元素，而任何一个元素都可能成为将来某个窗口的 median，一个都扔不得。

可行的结构是对顶堆：一个大顶堆装较小的一半、一个小顶堆装较大的一半，两堆规模差不超过 1，于是 median 只看一两个堆顶。窗口滑出的元素用惰性删除处理——不去堆里找它，而是记一笔账，等它浮到堆顶时再真正弹掉。

$[1, 3, -1, -3, 5, 3, 6, 7]$ 上， $k = 3$ 的 median 序列是 $[1, -1, -1, 3, 5, 6]$ ； $k = 4$ 时窗口内偶数个元素，取中间两个的平均，得 $[0, 1, 1, 4, 5.5]$ 。

图 4-1 · 滑动窗口 median 的对顶堆维护。左右两栏分别是较小一半与较大一半，中间标出当前 median。可改窗口宽度并对照逐窗排序的结果。

代价对照很悬殊。 $n = 20$ 万、 $k = 1000$ ，对顶堆 74 到 79 ms，逐窗排序 14.1 到 15.3 s，相差约 180 到 205 倍。这与monotonic deque 与定长窗口 §3 的情形相反。求最值时朴素解法只慢两三倍，因为它的内循环是紧凑的数值比较；求 median 的朴素解法每个窗口要做一次 $O(k \log k)$ 的排序并分配一个新数组，常数因子自己就把差距撑开了。堆的结构与实现细节见堆家族系列。

5 · 换结构的三条判据

同一个「区间聚合」需求，四种结构各有各的适用面。判据不是渐近复杂度，而是下面三条。

能不能扔掉元素。 单调栈与单调队列的全部效率来自「有些元素永远没用了」。求最值时这个判断成立，求 median、求第 $j$ 大、求和时都不成立。判据一旦不成立，就得换成堆或平衡结构。

查询区间是否等宽且顺序推进。 单调队列要求窗口宽度固定、且只从左向右滑一遍。区间任意或需要反复查，就得预处理：sparse table 建表 $O(n \log n)$ 、查询 $O(1)$ ，实测表格子数是 $16.7n$ ；区间查询系列里的线段树则支持带修改的查询，代价是每次 $O(\log n)$ 。

答案在哪一刻确定。 这一条决定能不能在线。prevGreater 一族在元素入栈时定答案，可以边来边答（§2 的股票跨度就是这个形态）；nextGreater 一族要等弹它的元素出现，天然是离线的。真正需要在线回答任意区间最值时，路线是 Cartesian tree 加 LCA，把 RMQ 归约成树上问题——见笛卡尔树：把 RMQ 变回 LCA。

6 · 参考文献

LeetCode 42 · Trapping Rain Water、901 · Online Stock Span、402 · Remove K Digits、480 · Sliding Window Median。本页四节的题面。
Gabow, H. N., Bentley, J. L., & Tarjan, R. E. (1984). Scaling and related techniques for geometry problems. Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 135–143. RMQ 到 LCA 的归约。
Bender, M. A., & Farach-Colton, M. (2000). The LCA problem revisited. LATIN 2000, 88–94. 线性预处理、常数查询的 RMQ 方案。
Vuillemin, J. (1980). A unifying look at data structures. Communications of the ACM, 23(4), 229–239. Cartesian tree 的原始定义，它与单调栈扫描是同一件事的两种写法。