接雨水（LeetCode #42）
接雨水计算高低柱之间能留下多少水。每列水位由左右两侧最高边界中较矮的一侧决定。关键是确定这些边界何时已经足够，再累计每列的非负深度。
接雨水如何工作
left_max[i] 是从开头到 i 的最高柱，right_max[i] 是从 i 到结尾的最高柱。第 i 列水深为：
min(left_max[i], right_max[i]) - height[i]
两个最大值都包含当前柱，因此差不会为负。只有一侧高不够，水会从较低边界流出。
前缀最大值法先构建两数组，再逐列套公式，时间 O(n)、额外空间 O(n)。双指针法只保存 left、right、left_max、right_max。
为什么能结算较小边界一侧
每步先更新当前端点的运行最大值，再比较。若 left_max <= right_max，右侧已见过至少与左边界同高的墙。中间未知柱可以提高右边界，却不能移除已经存在的墙。水又不可能超过左边界，因此当前左列最终水深就是 left_max - height[left]。
结算左列后向内移动。若 right_max < left_max，对称地结算右列。每次永久确定一列，不必再访问它。
逐步演示
默认 height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]，使用双指针。
- 指向列 0、11，运行最大值为 0、1，结算左列，水深 0。
- 列 1、2 继续从左结算，列 2 得到
1 - 0 = 1。 - 左到列 3，
left_max升为 2，right_max仍为 1，改为结算右列 11，水深 0。 - 右到列 10，
right_max升为 2。边界相等时选左，列 3、4、5、6 分别增加 0、1、2、1，总量到 5。 - 左到列 7，
left_max升为 3，右边界再次较小。列 10、9、8 分别增加 0、1、0。 - 只剩列 7，两端更新后的最大值相等，左分支结算水深 0，最终为 6。
切换前缀最大值法：左数组为 [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]，右数组为 [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]。逐列深度为 [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]，总和同为 6。
时间与空间复杂度
| 方法 | 时间 | 额外空间 | 保存内容 |
|---|---|---|---|
| 每列重扫两侧 | O(n²) | O(1) | 不保存边界 |
| 前缀最大值 | O(n) | O(n) | 左右最大值数组 |
| 双指针 | O(n) | O(1) | 两指针、两最大值 |
两种动画解法都是每列常数工作量：前缀最大值做三趟线性扫描，双指针每结算一列只做常数工作。编辑器最多 14 根柱，是显示限制。
“比较边界，再排除受较小边界限制的一侧”的证明也用于盛最多水的容器，但那里比较当前端点高度，不是运行最大值。前缀最大值则适合后续多次查询需要各方向最佳边界的场景。
边界情况
- 少于三根柱无法围住水。
- 空图、平坦平台或单调坡度的结果为 0。
- 最大值相等可以正常结算，本实现选择左侧。
- 零高度是正常柱位，不是数据缺失；深盆地单列可容纳多个单位。
- 首尾列各缺一侧外墙，水深始终为 0。
常见错误
- 用 max 而非 min。 会算出超过较低墙面的水。
- 混用两套不变量。 只比较端点高度，却用未更新的运行最大值结算，可能出错。
- 先移指针再记录当前列。 会漏列或把水量记到错误索引。
- 减法前不更新最大值。 可能出现负深度。
- 相等时不前进。 用一致的平局规则处理即可，不需要停住。