LeetCode 42：接雨水 —— 从“矩形法”到双指针的完整思考过程
题目链接：LeetCode 42 - Trapping Rain Water [page:2]
给定一个非负整数数组height，每个元素表示宽度为 1 的柱子的高度，问下雨后这些柱子之间能接多少水。[page:2]
示例：
height = [0,1,0,2,1,0,1,3,2,1,2,1]，输出6。[page:2]height = [4,2,0,3,2,5]，输出9。[page:2]
一、问题本质：单个位置能接多少水？
这是整个题目的根公式，也是双指针方法的基础：
对任意下标i，它上方能接的水量为：
[
water[i] = \max\bigl(0, \min(maxLeft[i], maxRight[i]) - height[i]\bigr)
]
其中：
maxLeft[i]：i左边（包含自己）最高的柱子高度。maxRight[i]：i右边（包含自己）最高的柱子高度。[page:2]
直观理解：
- 一格水的高度由“左边最高墙”和“右边最高墙”中较低的那一边决定。
- 如果这个“较低的墙”都比当前柱子矮，当然接不了水。
朴素做法：
- 预处理两个数组
maxLeft[]和maxRight[]，各自正反扫一遍得到每个位置的左右最高值。 - 再扫一遍数组，累加每个位置的
min(maxLeft[i], maxRight[i]) - height[i]（小于 0 则取 0）。[page:2]
时间复杂度 O(n)，空间复杂度 O(n)。优化方向也很明确：能不能把 O(n) 额外空间变成 O(1)？
二、第一次尝试：矩形法 + 左右边界
最开始的思路是这样的（简化表述）：
- 找到一个左边界柱子
start。 - 向右找第一个高度
>= height[start]的柱子作为右边界end。 - 此时
start..end之间的水量可以看作：- 用高度
height[start]和宽度(end - start)形成的“矩形面积”， - 再减去中间柱子自身占的面积。
- 用高度
这个思路本身没问题，很多人会写成类似这样（伪代码）：
从左往右找第一个非 0 的柱子作为 start i 从 start+1 往右扫： 如果 height[i] >= height[start]: // 找到右边界 end = i 计算 start 和 end 之间的水量： total = height[start] * (end - start - 1) // 中间格子个数 filled = sum(height[start+1 .. end-1]) water += total - filled start = end // 继续往右找下一段问题在于：当右侧一直找不到比start高/相等的柱子时，这种做法会漏算。例如：
- 输入
height = [5,4,1,2]：- 从左边 5 出发，右边没有高度
>= 5的柱子； - 但实际上，从右往左看，2 和 4 之间还是能接水的。[page:2]
- 从左边 5 出发，右边没有高度
为了补这个漏洞，常见做法是：
- 再从右向左做一遍同样的逻辑（用右边界开始），或者
- 引入栈，或者额外的辅助数组。
这种方案是可以 AC 的，但实现相对繁琐，且不如双指针写法简洁。
三、双指针法的核心思想
双指针法的目标是：用一次线性扫描，同时隐式维护“左侧最高”和“右侧最高”，且不需要数组，只要两个变量。[page:2]
1. 状态定义
我们维护四个量：
left：从左向右移动的指针；right：从右向左移动的指针；leftMax：height[0..left]区间内的最高柱子高度；rightMax：height[right..n-1]区间内的最高柱子高度。[page:2]
注意：leftMax和rightMax是“截至当前指针位置为止的局部信息”，但是我们会利用一个关键不变式，让它们足以决定当前格子能接的水量。
2. 关键不变式：每次推进较矮的一侧
核心规则：
- 当
height[left] < height[right]时，只处理left这一格，然后left++； - 当
height[left] >= height[right]时，只处理right这一格，然后right--。[page:2]
为什么可以只处理较矮的一边？
以height[left] < height[right]为例：
对位置
left来说，它的水量是：[
water[left] = \min(maxLeft[left], maxRight[left]) - height[left]
]此时我们已经有：
leftMax=max(height[0..left])；rightMax至少是height[right]，并且height[right] > height[left]。
对
left这一格而言，右侧最高值一定 ≥ 当前height[right]≥ 当前height[left]，所以“右边那堵墙”永远不会成为水位的短板。换句话说，
min(maxLeft, maxRight)一定等于maxLeft或更大，而height[left]是固定的。因此当前这格能接的水，实际上已经被leftMax决定了，右边即使将来再高也不会降低这格的水量上限。[page:2]
于是我们能得出结论：
- 当
height[left] < height[right]时，可以完全不用关心右边后续的变化，直接用leftMax来结算left的水量，然后安全地把left向右移动一格。 - 对称地，当
height[left] >= height[right]时，对right这一格而言，“左边的最高值”已经足够高，它的水量完全由rightMax决定，可以用同样的方式结算并right--。[page:2]
这就是“双指针只移动较矮的一侧”的数学和直觉依据。
四、双指针法的伪代码（思路级）
下面是不关心具体语言语法的思路级伪代码，只强调逻辑：
函数 trap(height, n): 如果 height 为空 或 n < 2: 返回 0 left = 0 right = n - 1 leftMax = 0 rightMax = 0 water = 0 当 left < right 时循环： 如果 height[left] < height[right]: 如果 height[left] >= leftMax: leftMax = height[left] # 更新左侧最高 否则： water += leftMax - height[left] # 当前格子可以接的水 left++ 否则： # height[left] >= height[right] 如果 height[right] >= rightMax: rightMax = height[right] # 更新右侧最高 否则： water += rightMax - height[right] right-- 返回 water关键点：
- 整个数组每个位置最多被访问一次，时间复杂度 O(n)。
- 只有常数级变量，空间复杂度 O(1)。
leftMax和rightMax在遍历过程中持续更新，相当于用两根指针“动态模拟”了maxLeft[]和maxRight[]的效果。[page:2]
五、最终 C 代码实现示例
下面是一个完整的 C 实现，符合上面的逻辑（与你提交并 AC 的代码结构一致）：[page:2]
inttrap(int*height,intheightSize){if(height==NULL||heightSize<2)return0;intleft=0;intright=heightSize-1;intleft_max=0;intright_max=0;intwater=0;while(left<right){if(height[left]<height[right]){// 右边有更高的墙接住 leftif(height[left]>left_max){left_max=height[left];}else{water+=left_max-height[left];}left++;}else{// 左边有更高的墙接住 rightif(height[right]>right_max){right_max=height[right];}else{water+=right_max-height[right];}right--;}}returnwater;}这段代码可以在 LeetCode 42 上通过所有测试，提交结果为：运行时间 0ms，击败 100% C 提交；内存使用约 10.48MB。[page:2]
六、小结：从直观到抽象的迁移
整个思考过程可以概括为三层：
- 直观层：把柱子之间看成一个个“凹槽”，用矩形面积减去柱子面积求水量。
- 公式层：抽象成每个位置的水量公式
[
water[i] = \min(maxLeft[i], maxRight[i]) - height[i]
] - 优化层：发现不需要显式存
maxLeft[]和maxRight[]，通过双指针和“只推进较矮一侧”的不变式，用两个变量leftMax/rightMax就能在线维护这些信息。[page:2]
理解了“为什么可以只移动较矮的一边”，双指针法就不再是模板，而是你自己推出来的算法。
如果你以后再遇到类似“左右边界决定中间位置上限”的题（如盛最多水、接雨水 II 等），都可以优先去想： - 能不能找到某种不变式，让我每次安全地丢弃一侧？ - 能不能用两个指针 + 局部最大值，隐式维护全局信息？这一题就是非常经典的例子。