接雨水为什么可以用双指针一趟求解？leftMax 和 rightMax 怎么理解？

简化版

接雨水的水量由左右两侧最高柱子的较小值决定：water[i] = min(leftMax, rightMax) - height[i]。双指针从两端向中间走，维护 leftMax 和 rightMax；哪边最大值更小，就先结算哪边，因为那边的水位上限已经确定。时间 O(n)，空间 O(1)。

详细版

对位置 i，能接多少水取决于左边最高墙和右边最高墙中较矮的那堵墙。预处理数组可以分别求每个位置的 leftMax[i] 和 rightMax[i]，再累加 min(leftMax[i], rightMax[i]) - height[i]，但需要 O(n) 额外空间。

双指针优化的思路是只保存当前左右边界的最高值。若 leftMax <= rightMax，说明左侧当前位置的水位最多只能被 leftMax 限制，右侧已经有不低于它的墙兜底，所以可以结算左边并移动 left；反之结算右边。

例如 height = [0,1,0,2,1,0,1,3,2,1,2,1]，答案是 6。面试重点是解释“为什么移动较小 max 的一侧是安全的”，而不是只背代码。

完整版教学

一、水位公式从哪里来

某个格子能装水，必须左右两侧都有墙。左边最高墙是 L，右边最高墙是 R，水位不可能超过较矮的墙，所以可装水高度是 min(L, R) - height[i]，如果结果为负就按 0 处理。

对下标 5，假设 height[5]=0，左侧最高是 2，右侧最高是 3，那么水位是 min(2,3)=2，该格能接 2 单位水。这个公式是所有接雨水解法的基础。

water[i] = max(0, min(max(height[0..i]), max(height[i..n-1])) - height[i])

记忆钩子：接雨水不是看旁边一根柱子，而是看“左边最高”和“右边最高”这两堵墙。

二、预处理解法为什么能优化

直接为每个位置向左、向右扫描最高值，会变成 O(n^2)。预处理 leftMax[] 和 rightMax[] 可以把最高值查询降到 O(1)，总代价 O(n) 时间、O(n) 空间。

双指针进一步观察：结算某一侧时，不一定需要知道另一侧的精确最大值，只要知道另一侧已经有一堵不矮于当前侧最高值的墙。于是 leftMax <= rightMax 时，左侧位置的水位上限已经由 leftMax 决定。

解法	时间	空间	关键思想
每格左右扫描	O(n^2)	O(1)	直接套公式
前后缀最大值	O(n)	O(n)	提前保存左右最高
双指针	O(n)	O(1)	只结算上限已确定的一侧

三、为什么移动较小 max 的一侧

假设当前 leftMax <= rightMax。对 left 指向的位置来说，右边至少存在高度为 rightMax 的墙，而 rightMax 不低于 leftMax，所以它的水位一定由左侧 leftMax 限制。即使右边未来还有更高的墙，也不会改变 min(leftMax, rightMax) 的结果。

这就是安全移动左指针的原因。反过来，如果 rightMax < leftMax，右侧位置的水位一定由 rightMax 限制，可以结算右边。

leftMax <= rightMax
左侧格子的水位 = leftMax - height[left]
右侧未来再高，也不会让 min(leftMax, rightMax) 超过 leftMax

四、代码模板

代码里先更新当前柱子对 leftMax/rightMax 的贡献，再根据较小的一侧结算。另一种写法是先判断再更新，也可以，但要保证不出现负水量。

int trap(int[] height) {
    int l = 0, r = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int ans = 0;
    while (l < r) {
        leftMax = Math.max(leftMax, height[l]);
        rightMax = Math.max(rightMax, height[r]);
        if (leftMax <= rightMax) {
            ans += leftMax - height[l];
            l++;
        } else {
            ans += rightMax - height[r];
            r--;
        }
    }
    return ans;
}

ans += leftMax - height[l] 不会为负，因为 leftMax 已经包含当前高度。这个细节能减少很多边界判断。

五、带数字手推

以 [4,2,0,3,2,5] 为例，答案是 9。开始 l=0,r=5,leftMax=4,rightMax=5，因为左边较小，结算左侧：第 0 格水量 0，l=1。

第 1 格高度 2，leftMax=4,rightMax=5，水量 4-2=2；第 2 格高度 0，水量 4-0=4；第 3 格高度 3，水量 4-3=1；第 4 格高度 2，水量 4-2=2。总水量 0+2+4+1+2=9。

height: 4 2 0 3 2 5
water : 0 2 4 1 2 0
sum   : 9

六、常见误区与追问

误区：只看相邻两根柱子。 水能不能存住取决于两侧最高墙，不是左右邻居。
误区：总是移动高度较小的一侧。 更稳的解释是移动 leftMax/rightMax 较小的一侧；某些代码用当前高度比较也能成立，但面试解释更容易绕。
误区：忘记更新 max 就累加水量。 如果当前柱子比历史最高还高，应该先抬高边界，而不是加负水量。
追问：为什么双指针不需要前缀数组？ 因为每次只结算水位上限已确定的一侧，不需要知道每个位置完整的左右最大值。
追问：如果数组长度小于 3 怎么办？ 无法形成左右边界，循环自然返回 0，也可以提前判断。
追问：空间复杂度为什么是 O(1)？ 除了几个整数指针和最大值，没有随 n 增长的额外结构。

七、和盛最多水容器的区别

两题都用相向双指针，但目标完全不同。盛最多水容器选两根柱子形成一个容器，面积是 min(h[l], h[r]) * width；接雨水要计算每个位置上方能存多少水，需要左右最高墙。

题目	关注对象	移动依据	结果
盛最多水容器	两根边界柱	较矮柱限制面积	最大面积
接雨水	每个位置水量	较小 max 决定水位	总水量

把两题混写是高频错误。容器题不需要 leftMax/rightMax，接雨水题不直接用宽度乘高度。

八、加强记忆

接雨水的核心链路是：每格水量看左右最高墙，水位取较小者；双指针只是在省掉前后缀数组，每次结算“较小 max 那一侧”。背代码前先记住安全性证明：另一侧已经有足够高的墙兜底，当前侧的上限不会再被未来改变。

简化版

详细版