LeetCode 第42题 接雨水
class Solution { public int trap(int[] height) { int ans = 0; // 保存总共承接雨水总量 int left = 0, right = height.length - 1; // 左右双指针 int leftMax = 0, rightMax = 0; // left左侧最高柱子、right右侧最高柱子 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; } }一、核心算法思想（双指针 O (n)、空间 O (1)）
基础理论：单个位置蓄水量 = min (当前位置左侧最高柱子，当前位置右侧最高柱子) − 当前柱子高度
- 定义左指针
left起始于数组头部，右指针right起始于数组尾部； leftMax：记录左指针遍历路径上的最高柱子；rightMax：记录右指针遍历路径上的最高柱子；- 短板判定规则：
- 如果
height[left] < height[right]：左侧为短板。此时leftMax就是左右两侧较小的最大值，直接计算当前 left 位置雨水，左指针右移； - 如果
height[left] >= height[right]：右侧为短板。此时rightMax就是左右两侧较小的最大值，直接计算当前 right 位置雨水，右指针左移；
- 如果
- 累加每个位置蓄水量，指针相遇循环结束，返回雨水总和。
记忆口诀：哪边柱子矮，先算哪边蓄水量，移动哪边指针。
二、实例运行表格推演
测试样例：height = [0,1,0,2,1,0,1,3,2,1,2,1]
初始状态：left=0，right=11，leftMax=0，rightMax=0，ans=0
| left | right | height[left] | height[right] | leftMax | rightMax | 大小对比 | 当前格子雨水 | 总水量 ans |
|---|---|---|---|---|---|---|---|---|
| 0 | 11 | 0 | 1 | 0 | 1 | left 矮 | 0-0=0 | 0 |
| 1 | 11 | 1 | 1 | 1 | 1 | 相等，走右侧逻辑 | 1-1=0 | 0 |
| 1 | 10 | 1 | 2 | 1 | 2 | left 矮 | 1-1=0 | 0 |
| 2 | 10 | 0 | 2 | 1 | 2 | left 矮 | 1-0=1 | 1 |
| 3 | 10 | 2 | 2 | 2 | 2 | 相等，走右侧逻辑 | 2-2=0 | 1 |
| 3 | 9 | 2 | 1 | 2 | 2 | right 矮 | 2-1=1 | 2 |
| 3 | 8 | 2 | 2 | 2 | 2 | 相等，走右侧逻辑 | 2-2=0 | 2 |
| 3 | 7 | 2 | 3 | 2 | 3 | left 矮 | 2-2=0 | 2 |
| 4 | 7 | 1 | 3 | 2 | 3 | left 矮 | 2-1=1 | 3 |
| 5 | 7 | 0 | 3 | 2 | 3 | left 矮 | 2-0=2 | 5 |
| 6 | 7 | 1 | 3 | 2 | 3 | left 矮 | 2-1=1 | 6 |
循环终止条件：left=7，right=7，不满足left<right，最终总雨水ans=6。
三、易错点与知识点总结
1. 容易混淆题目区分
LeetCode 11【盛最多水的容器】 VS LeetCode 42【接雨水】
- 11 题：求两根柱子之间形成的矩形面积，整体区间蓄水；
- 42 题：逐根竖柱单独计算垂直方向雨水，每个位置受左右最高柱子限制，两道题模型完全不同，不要混用思路。
2. 核心概念误区
leftMax和rightMax不是全局最大值，只是指针行进路径上记录的最大值。依靠「短板效应」，不需要预先开辟数组存储每个位置左右最大值，实现 O (1) 空间复杂度。
3. 蓄水量不会为负数
leftMax永远大于等于height[left]；rightMax永远大于等于height[right]，因此计算出的雨水数值≥0，无需额外判断。