42. 接雨水
3 min
题目
思路
核心思想是双指针贪心算法，通过维护左右指针和两侧最大高度值，每次移动高度较小的一侧指针并累加雨水量。
正确性基于木桶原理：当前位置的积水量由左右最大高度的较小值决定。当左指针高度小于右指针时，左指针位置的积水量仅取决于左侧最大高度（因为右侧最大高度已足够高且不会小于当前右指针高度），移动左指针不会遗漏最优解；反之亦然。这种策略确保每个位置在指针移动过程中被精确计算一次。
- Step 1: 初始化左右指针和左右最大高度变量
- Step 2: 循环比较左右指针高度，更新对应侧最大高度
- Step 3: 根据较小高度侧计算积水量并移动指针
- Step 4: 循环结束后返回累加结果
复杂度
- 时间复杂度: ，每个元素仅被访问一次，瓶颈在双指针的线性扫描过程。
- 空间复杂度: ，仅使用固定数量的指针和高度变量，无额外数据结构。
代码
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}