LeetCode 42. 接雨水
题目描述
✅ 42. 接雨水
题意分析
height[i]表示第i根柱子的高度，每根柱子的宽度为1。雨水只能停留在柱子之间有左右挡板的位置，要求计算所有位置积水的总体积。这里不是任选两根柱子围出一个容器，而是固定整组柱子，汇总每一列真正能存下的水。挡板不一定紧挨当前列；单调排列或全部等高时无法形成低洼区域，总水量为
0。
解法：前后缀最大值
核心思路
[!blue]
先单独看第
i列。雨水要停在这一列上方，左侧和右侧都必须有足够高的柱子挡住。设leftMax[i]是从开头到i的最高柱，rightMax[i]是从i到末尾的最高柱，两边都包含当前柱子。水位不可能超过这两个最高值中较小的一个，否则会从较低的一侧流走；两边又确实分别存在达到该高度的挡板，所以该水位能够维持。于是这一列的水深是
min(leftMax[i], rightMax[i]) - height[i]。每列宽度为1，水深也就是这一列的水量，把各列相加就是答案。如果对每列都重新向两侧寻找最高柱，会重复扫描。前缀最大值满足
leftMax[i] = max(leftMax[i - 1], height[i])，从左到右即可求完；后缀最大值同理，从右到左求出。这样预处理和最后求和都只需线性扫描。把当前柱也计入两侧最大值，能保证水深不会为负。最左端的前缀最大值就是自身，最右端的后缀最大值也是自身，所以边缘列自然贡献
0，不需要单独排除。
解题步骤
- 创建长度为
n的leftMax、rightMax数组。- 令
leftMax[0] = height[0]，从左到右用前一项与当前柱高的较大值更新前缀最大值。- 令
rightMax[n - 1] = height[n - 1]，从右到左用后一项与当前柱高的较大值更新后缀最大值。- 遍历每列，累加
min(leftMax[i], rightMax[i]) - height[i]，返回总和。题目保证至少有一根柱子，两端初始化合法。
代码实现
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
rightMax[n - 1] = height[n - 1];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int water = 0;
for (int i = 0; i < n; i++) {
water += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
}
func trap(height []int) int {
n := len(height)
leftMax := make([]int, n)
rightMax := make([]int, n)
leftMax[0] = height[0]
rightMax[n-1] = height[n-1]
for i := 1; i < n; i++ {
leftMax[i] = max(leftMax[i-1], height[i])
}
for i := n - 2; i >= 0; i-- {
rightMax[i] = max(rightMax[i+1], height[i])
}
water := 0
for i := range height {
water += min(leftMax[i], rightMax[i]) - height[i]
}
return water
}
复杂度分析
- 时间复杂度：$O(n)$，分别计算前缀、后缀最大值，再求和，共三次线性扫描。
- 空间复杂度：$O(n)$，保存两个长度为
n的辅助数组。
关键点总结
[!green]
- 先确定每一列的水位，再减去柱子自身高度，最后累加各列水量。
- 左右最高挡板限制的是同一列，必须取两者较小值。
- 前后缀最大值避免重复扫描，也为双指针进一步压缩空间提供了依据。
解法：双指针
核心思路
[!blue]
前后缀解法为每一列预先求出了两侧最高值。双指针进一步利用一个事实：当一侧已经确定了水位上限，而另一侧确定存在不低于这个上限的挡板时，就不需要知道另一侧的精确最大值，也能立即结算当前列。
令
left、right指向尚未结算区间的两端，leftMax、rightMax分别记录两端已经处理过的最高柱。每轮比较两个端点的当前柱高，只结算较矮的一端。以
height[left] <= height[right]为例。如果当前左柱不低于leftMax，它本身就是左侧最高柱，当前列没有水，只需更新leftMax。如果它低于leftMax，当前列左边就有高度为leftMax的挡板；这根挡板当初也是作为较矮端被处理的，所以当时右侧已有不低于它的柱子。那根右侧柱子即使后来被指针越过，仍然真实地位于当前列右边，挡水条件不会消失。因此当前列的水位恰好由leftMax决定，水量为leftMax - height[left]。右端较矮时完全对称，用
rightMax判断是否积水。结算后只移动这一侧的指针，每列只计算一次。两指针相遇时可以停止：每次删除的端点都不高于另一端，所以至少一根全局最高柱会一直留在未处理区间中，最后剩下的位置就是其中一根。最高柱顶上不可能存水，无需再结算。
解题步骤
- 令
left = 0、right = n - 1，两侧历史最大高度及总水量均为0。- 在
left < right时比较两端柱高。左端较矮或等高，就处理左端；否则处理右端。- 若当前柱高不低于本侧历史最大值，更新最大值；否则累加两者的高度差。
- 向内移动刚刚处理的一侧，另一侧保持不动。
- 两指针相遇后返回总水量；只有一根柱子时循环不会执行，直接返回
0。
代码实现
class Solution {
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int water = 0;
while (left < right) {
// 结算较矮的一端，对侧已有挡板保证本侧计算有效。
if (height[left] <= height[right]) {
if (height[left] >= leftMax) {
// 当前列成为更高挡板，只更新历史最大值，不贡献积水。
leftMax = height[left];
} else {
// 本列低于历史挡板，差值就是该列积水。
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
}
func trap(height []int) int {
left, right := 0, len(height)-1
leftMax, rightMax, water := 0, 0, 0
for left < right {
// 结算较矮的一端，对侧已有挡板保证本侧计算有效。
if height[left] <= height[right] {
if height[left] >= leftMax {
// 当前列成为更高挡板，只更新历史最大值，不贡献积水。
leftMax = height[left]
} else {
// 本列低于历史挡板，差值就是该列积水。
water += leftMax - height[left]
}
left++
} else {
if height[right] >= rightMax {
rightMax = height[right]
} else {
water += rightMax - height[right]
}
right--
}
}
return water
}
复杂度分析
- 时间复杂度：$O(n)$，每轮把尚未处理的区间缩短一列，不会回退。
- 空间复杂度：$O(1)$，只保存两个指针、两个历史最大高度和累计水量。
关键点总结
[!green]
- 双指针省去的是每一列两侧最大值的存储，计算依据仍是较低的最高挡板限制水位。
- 历史挡板被指针越过，只表示它已经结算，不表示它从柱状图中消失。
- 每轮只结算有充分挡水依据的一端，最后剩下的最高柱贡献为
0。
易错点总结
[!yellow]
- 水位取两侧最高值的较小者，较高的一边无法阻止雨水从较低的一边流走。
- 前后缀最大值要包含当前柱子，否则高度差可能为负，还需要额外处理边界。
- 双指针比较的是当前两端柱高，计算水量使用的是本侧历史最大值，不能把两者混淆。
- 当前柱刷新本侧最大值时贡献为
0，不能先用较小的旧最大值相减而累加负数。- 不能先结算较高端：这时对侧未必有足够高的挡板，本侧历史最大值也就未必等于真实水位。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 407. 接雨水 II | 困难 | 从一维左右边界推广到二维四邻边界，原题需要最小堆从最低外边界向内扩散。 |
| 11. 盛最多水的容器 | 中等 | 两题都受较低边界限制，但容器题只选两柱，接雨水要汇总每个位置的水深。 |