接雨水
Trapping Rain Water
给定柱子的高度数组，计算下雨后这些柱子之间能接住多少单位的雨水。
在力扣中练习题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
解题思路
双指针 · 较矮一侧定水位
左右各维护最大高度，较矮的一侧先结算
单独看第 i 列，它能接的水是 min(左边最高, 右边最高) - height[i]。但每次都往两边扫一遍是 O(n²)。
双指针从两端向中间收，同时维护 leftMax 和 rightMax。关键观察：如果 leftMax < rightMax，那么左侧当前列的水位由 leftMax 决定——右边一定存在一根不低于 rightMax 的柱子，已经足够当挡板。于是可以立刻结算左列，然后右移。
反过来，rightMax ≤ leftMax 时先结算右列。每列只结算一次。
自拟主例 [3,0,2,0,4,1,2] 的积水量是 [0,3,1,3,0,1,0]，总和 8。
rightMax 2 ≤ leftMax 3，右边界能接 0 格水；right 左移。
- rightMax
- 2
- water
- 0
时间 O(n)，空间 O(1)。双指针版本把这两个数组压成变量，边扫边维护。
leftMax 3 < rightMax 4，左边界能接 1 格水；left 右移。
- leftMax
- 3
- water
- 5
易错点
- 用 height[left] 当水位：水位由左右两侧的最大高度共同决定，不是当前柱子。
- 不维护 leftMax / rightMax 就结算：会得到负水量或偏小的结果。
- 移动较高的一侧：较矮一侧还没结算，水位判断会失去依据。
前缀最大值 · 两次扫描
先预处理每列左边和右边的最高柱子
时间同为 O(n)，但需要两个 O(n) 数组；思路上更直观，适合先写出正确版本再压缩空间。
把 min(左边最高, 右边最高) 拆成两个数组：
leftMax[i]：从 0 到 i 的最高柱子；rightMax[i]：从 i 到 n-1 的最高柱子。
两者都能用一次递推求出，然后每一列的水量就是 min(leftMax[i], rightMax[i]) - height[i]。
时间 O(n)，空间 O(n)。双指针版本就是把这两个数组压成两个变量，边扫边维护。
- 1从左到右求 leftMax。
- 2从右到左求 rightMax。
- 3逐列累加 min(leftMax[i], rightMax[i]) - height[i]。
易错点
- rightMax 从右往左求时用了 i+1 之外的错误方向：会得到局部最大值。
- 忘记 n == 0 的特判：访问 height[0] 越界。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
height = [3,0,2,0,4,1,2]left = 0，right = 6；leftMax / rightMax 先设为 0。
- water
- 0
查看 C++ 代码
延伸阅读
- “每列的水量 = min(左最高, 右最高) - 当前高度”是接雨水的核心；不同做法只是维护这两个最大值的方式不同。
- 二维接雨水（407）需要优先队列从边界向内收缩，思路变成“先处理当前最矮的边界”。