接雨水

怎样从“高度 [0,1,0,2,1,0,1,3,2,1,2,1],求能接的雨水总量。”推导出 双指针 · 接雨水，并证明每次状态变化都不会漏掉答案？

中心结论：双指针维护 leftMax/rightMax;较低一侧决定当前列积水。

从 x 轴开始，给出一个数组，数组里面的数字代表从 (0,0) 点开始，宽度为 1 个单位，高度为数组元素的值。如果下雨了，问这样一个容器能装多少单位的水？

在本站主例中，高度 [0,1,0,2,1,0,1,3,2,1,2,1],求能接的雨水总量。

算法最终需要得到或观察：总接水量 6。

为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“单调候选队列”，明确答案需要观察什么。
2. 2状态只维护 L/R、leftMax、rightMax、累计水量。
3. 3转移每一步按照 双指针维护 leftMax/rightMax;较低一侧决定当前列积水。
4. 4收尾读取 总接水量 6。，并复核边界与复杂度。

栈或队列中保存的是仍未找到结论、且保持单调关系的下标。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：L/R、leftMax、rightMax、累计水量。

每个数组里面的元素值可以想象成一个左右都有壁的圆柱筒。例如下图中左边的第二个元素 1，当前左边最大的元素是 2 ，所以 2 高度的水会装到 1 的上面(因为想象成了左右都有筒壁)。这道题的思路就是左指针从 0 开始往右扫，右指针从最右边开始往左扫。额外还需要 2 个变量分别记住左边最大的高度和右边最大高度。遍历扫数组元素的过程中，如果左指针的高度比右指针的高度小，就不断的移动左指针，否则移动右指针。循环的终止条件就是左右指针碰上以后就结束。只要数组中元素的高度比保存的局部最大高度小，就累加 res 的值，否则更新局部最大高度。最终解就是 res 的值。

抽象一下，本题是想求针对每个 i，找到它左边最大值 leftMax，右边的最大值 rightMax，然后 min(leftMax，rightMax) 为能够接到水的高度。left 和 right 指针是两边往中间移动的游标指针。最傻的解题思路是针对每个下标 i，往左循环找到第一个最大值，往右循环找到第一个最大值，然后把这两个最大值取出最小者，即为当前雨水的高度。这样做时间复杂度高，浪费了很多循环。i 在从左往右的过程中，是可以动态维护最大值的。右边的最大值用右边的游标指针来维护。从左往右扫一遍下标，和，从两边往中间遍历一遍下标，是相同的结果，每个下标都遍历了一次。

每个 i 的宽度固定为 1，所以每个“坑”只需要求出高度，即当前这个“坑”能积攒的雨水。最后依次将每个“坑”中的雨水相加即是能接到的雨水数。

双指针维护 leftMax/rightMax;较低一侧决定当前列积水。

执行过程中持续维护：L/R、leftMax、rightMax、累计水量。

正确性依赖以下不变量：较低侧 max 确定该侧边界,可安全计算该侧指针列。

面试时可以压缩为：双指针:L/R 两端,矮侧更新 max 并累加雨水,矮侧内移,O(n)。

落到当前题，执行机制可以压缩为：双指针维护 leftMax/rightMax;较低一侧决定当前列积水。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入高度 [0,1,0,2,1,0,1,3,2,1,2,1],求能接的雨水总量。 因为：双指针维护 leftMax/rightMax;较低一侧决定当前列积水。
2. 2左指针 0:积水 +0, lMax=0左指针右移。 因为：右侧更高,左侧由 lMax 限制。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4右指针 11:积水 +0, rMax=1右指针左移。 因为：对称逻辑。
5. 5左指针 3:积水 +0, lMax=2左指针右移。 因为：右侧更高,左侧由 lMax 限制。
6. 6左指针 5:积水 +2, lMax=2左指针右移。 因为：右侧更高,左侧由 lMax 限制。
7. 7右指针 10:积水 +0, rMax=2右指针左移。 因为：对称逻辑。
8. 8收尾与复杂度总接水量 6。 因为：时间 O(n) · 空间 O(1)。双指针维护 leftMax/rightMax;较低一侧决定当前列积水。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func trap(height []int) int {
	res, left, right, maxLeft, maxRight := 0, 0, len(height)-1, 0, 0
	for left <= right {
		if height[left] <= height[right] {
			if height[left] > maxLeft {
				maxLeft = height[left]
			} else {
				res += maxLeft - height[left]
			}
			left++
		} else {
			if height[right] >= maxRight {
				maxRight = height[right]
			} else {
				res += maxRight - height[right]
			}
			right--
		}
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="trapping-rain", heights=[0,1,0,2,1,0,1,3,2,1,2,1]
    //    期望：总接水量 6。
    //
    // 2. 失败 / 未命中
    //    检查：逐列暴力需 RMQ;双指针 O(n) 关键在移动较矮侧。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC11 盛水；LC84 柱状矩形
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意高度 [0,1,0,2,1,0,1,3,2,1,2,1],求能接的雨水总量。
2. 2重复为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
3. 3优化双指针维护 leftMax/rightMax;较低一侧决定当前列积水。
4. 4证明较低侧 max 确定该侧边界,可安全计算该侧指针列。
5. 5复杂度时间 O(n)，空间 O(1)