接雨水：从按列计算理解双指针解法
1. 这道题真正容易卡在哪里
LeetCode 42「接雨水」这道题，很多人第一次看双指针解法时，最难理解的往往不是代码语法，而是计算模型。
官方题解里的代码大概是这样：
classSolution{public:inttrap(vector<int>&height){intans=0;intleft=0,right=height.size()-1;intleftMax=0,rightMax=0;while(left<right){leftMax=max(leftMax,height[left]);rightMax=max(rightMax,height[right]);if(height[left]<height[right]){ans+=leftMax-height[left];++left;}else{ans+=rightMax-height[right];--right;}}returnans;}};其中最容易让人疑惑的是这一句：
ans+=leftMax-height[left];为什么当前位置的积水量可以直接用leftMax - height[left]？为什么不用右边最高柱子？为什么每次移动一个指针就能把一列的水算完？
这些疑惑的根源通常是：我们一开始把这道题想成了“水怎么流、怎么一层一层填”的模拟题。但这道题的核心其实不是模拟水流，而是计算每一列最终能存多少水。
也就是说，这题应该统一成一个视角：
按列计算，每次确定某一个位置这一整列最终能接多少水。只要这个视角稳定下来，双指针代码就会顺很多。
2. 先纠正一个常见误区：y 坐标轴不是挡板
画柱状图时，我们经常会看到左边有一个纵轴。这个纵轴只是高度刻度，不是现实中的墙。
真正能挡水的，只有数组里的柱子：
height[0],height[1],height[2],...,height[n-1]数组外侧没有柱子。比如最左边位置的左侧是空的，不是一堵墙。所以数组两端通常不能积水，因为它们缺少一侧边界。
这点很重要，因为如果误把 y 坐标轴当成挡板，就会错误地认为靠近边界的位置也能接水，从而破坏对题目的基本理解。
3. 第一性原理：一个位置能接多少水
先不管双指针。我们只看某一个位置i。
位置i能接多少水，取决于三件事：
1. 当前柱子高度 height[i] 2. 它左边最高的柱子 3. 它右边最高的柱子水面高度不能超过左右两侧较矮的那一边。因为如果左边最高是 5，右边最高是 3，那么水最多只能到高度 3，再高就会从右边流走。
所以位置i的最终水面高度是：
min(左边最高柱子,右边最高柱子)当前位置的积水量就是：
min(左边最高柱子,右边最高柱子)-height[i]也就是：
water[i]=min(leftMax[i],rightMax[i])-height[i];这就是整道题最核心的公式。
所有解法，本质上都是围绕这条公式展开：
每一列水量 = 左右最高柱子的较小值 - 当前柱子高度4. 为什么说这是“按列计算”
比如：
height = [3, 0, 2, 0, 4]如果按列来看：
位置 0：左边最高 3，右边最高 4，当前高度 3，积水 0 位置 1：左边最高 3，右边最高 4，当前高度 0，积水 3 位置 2：左边最高 3，右边最高 4，当前高度 2，积水 1 位置 3：左边最高 3，右边最高 4，当前高度 0，积水 3 位置 4：左边最高 4，右边最高 4，当前高度 4，积水 0总水量是：
0 + 3 + 1 + 3 + 0 = 7注意这里没有模拟水从哪里流来，也没有一层一层填水。我们只是对每个位置直接计算最终水深。
这就是“按列计算”。
它和“按行填充”的思路不同。按行填充会想：第一层哪些格子能存水，第二层哪些格子能存水，第三层哪些格子能存水。但双指针不是这种思路。
双指针的思路是：
每次找一个已经能确定最终水量的位置，把这一列一次性结算掉。5. 从暴力解法推到双指针
下次重新做这道题时，不要一上来背双指针代码。更自然的推导路线是从最朴素的方法开始。
对于每个位置i：
1. 向左扫描，找到左边最高柱子 2. 向右扫描，找到右边最高柱子 3. 用较小值减去当前高度伪代码是：
for每个位置 i:leftMax=i 左边最高柱子 rightMax=i 右边最高柱子 ans+=min(leftMax,rightMax)-height[i]这个方法容易理解，但时间复杂度是O(n^2)，因为每个位置都要重新扫描左右两边。
然后自然想到优化：
既然每个位置都需要左边最高和右边最高，那能不能提前算好？于是得到预处理数组解法：
leftMax[i]=从0到 i 的最高柱子 rightMax[i]=从 i 到 n-1的最高柱子再遍历一次：
ans+=min(leftMax[i],rightMax[i])-height[i];这个方法时间复杂度是O(n)，空间复杂度是O(n)。
接下来继续问：
我真的需要把所有位置的 leftMax 和 rightMax 都存下来吗？其实不一定。因为我们不需要一次性知道所有位置的信息，只需要每次确定一个位置的积水量。
这时就可以想到双指针。
6. left 和 right 到底表示什么
双指针代码里：
intleft=0,right=height.size()-1;left和right不是最终的左右挡板，也不是在找一对固定的墙。
它们更准确的含义是：
left：当前还没有结算的最左位置 right：当前还没有结算的最右位置也就是说，区间[left, right]表示当前还没处理的范围。
每一轮循环，算法都会结算掉一个端点位置：
如果结算 left 这一列，就 left++ 如果结算 right 这一列，就 right--所以双指针不是在模拟水流，而是在不断缩小“未结算区间”。
7. leftMax 和 rightMax 表示什么
代码里还有两个变量：
intleftMax=0,rightMax=0;它们的含义是：
leftMax：从数组最左端到当前 left 位置为止，见过的最高柱子 rightMax：从数组最右端到当前 right 位置为止，见过的最高柱子每轮循环开头更新：
leftMax=max(leftMax,height[left]);rightMax=max(rightMax,height[right]);意思是：
先把当前 left 和 right 位置也纳入两侧最高柱子的统计。这样做之后，如果后面要结算left，那么leftMax已经包含当前位置；如果要结算right，那么rightMax也已经包含当前位置。
因此：
leftMax-height[left]rightMax-height[right]不会是负数。
8. 为什么哪边矮就先结算哪边
核心判断是：
if(height[left]<height[right]){ans+=leftMax-height[left];++left;}else{ans+=rightMax-height[right];--right;}这段代码不是在问“哪边能接更多水”，而是在问：
当前 left 和 right 这两个端点，哪一列的答案已经可以确定？如果：
height[left]<height[right]说明在left的右侧，至少存在一根柱子，就是height[right]，并且它比height[left]高。
所以对于left这一列来说：
右边有挡板这个事实已经成立。既然右边有挡板，当前left这一列能接多少水，就只需要看左侧目前最高柱子leftMax。
于是可以直接结算：
ans+=leftMax-height[left];这句话的含义是：
当前 left 这一列的最终水位由 leftMax 决定。 当前柱子高度是 height[left]。 所以这一列水深 = leftMax - height[left]。反过来，如果：
height[left]>=height[right]说明在right的左侧，至少存在一根柱子，就是height[left]，并且它不低于height[right]。
所以对于right这一列来说：
左边有挡板这个事实已经成立。此时可以结算右边：
ans+=rightMax-height[right];也就是：
当前 right 这一列的最终水位由 rightMax 决定。 当前柱子高度是 height[right]。 所以这一列水深 = rightMax - height[right]。9. 为什么不是把水当成新挡板
有一种直觉是：前面已经算出来的水可以当成真实挡板，然后继续往后算。
这个直觉能帮助我们从“按行填充”切换到“按列结算”，但严格来说不准确。
水本身不能当挡板。真正决定某一列能不能积水的，仍然是左右两边真实存在的柱子。
比如：
height = [5, 0, 0, 0, 1]中间位置最多只能接到高度1，因为右边最高的真实柱子只有1。不能因为左边有高度5，也不能因为前面已经算出了一些水，就把水面继续垒到高度5。
所以更准确的理解是：
已经结算过的位置，它的最终水量已经确定，不需要再参与后续计算。 后续位置能不能积水，仍然由真实柱子形成的左右边界决定。也就是说：
不是水变成了挡板。 而是某一列的最终水位已经被真实边界确定，所以可以封账。10. 为什么循环条件是 left < right
代码里循环条件是：
while(left<right)当left == right时，确实可能还有一个位置没有被单独结算过。
比如：
height = [0, 1, 0]最后可能剩下中间的1没有被单独计算。但它本身是最高柱子，积水量是0，所以不影响答案。
关键不是“最后这个位置一定算过”，而是：
最后剩下的这个位置即使没算，它的贡献也一定是 0。如果某个中间位置真的能积水，它不会被留到left == right才处理。
例如：
height = [3, 0, 3]中间的0能接 3 格水。双指针过程中，它会在指针相遇之前作为右端点被结算：
ans+=rightMax-height[right];得到：
3 - 0 = 3所以while (left < right)的含义可以写得更严谨一些：
只要未处理区间至少有两个位置，就继续从两端选择一个可确定的位置结算。 当 left == right 时，剩下的唯一位置即使没有被单独结算，它的贡献也一定是 0。11. 完整注释版代码
classSolution{public:inttrap(vector<int>&height){intans=0;// left 表示当前还没有结算的最左位置// right 表示当前还没有结算的最右位置// 未处理区间是 [left, right]intleft=0,right=height.size()-1;// leftMax 表示从数组最左端到当前 left 位置为止，见过的最高柱子// rightMax 表示从数组最右端到当前 right 位置为止，见过的最高柱子intleftMax=0,rightMax=0;// 每一轮循环都会结算一个端点位置：// 要么结算 left 这一列，要么结算 right 这一列。// 当 left == right 时，剩下的唯一位置即使没有被单独结算，贡献也一定是 0。while(left<right){// 先把当前 left 和 right 位置纳入两侧最高柱子的统计leftMax=max(leftMax,height[left]);rightMax=max(rightMax,height[right]);// 如果左端当前柱子更矮，说明 left 的右侧至少有 height[right] 这根柱子作为右边界。// 因此 left 这一列的积水量已经可以确定。// 当前列水量 = 左侧最高水位 leftMax - 当前柱子高度 height[left]if(height[left]<height[right]){ans+=leftMax-height[left];++left;}// 否则，右端当前柱子更矮或者两边一样高。// 说明 right 的左侧至少有 height[left] 这根柱子作为左边界。// 因此 right 这一列的积水量已经可以确定。// 当前列水量 = 右侧最高水位 rightMax - 当前柱子高度 height[right]else{ans+=rightMax-height[right];--right;}}returnans;}};12. 用一个例子完整走一遍
看这个数组：
height = [3, 0, 2, 0, 4]初始：
left = 0 right = 4 leftMax = 0 rightMax = 0 ans = 0第一轮：
height[left] = 3 height[right] = 4 leftMax = 3 rightMax = 4因为：
3<4所以结算左边：
ans+=3-3=0left++位置 0 是边界柱子，不积水。
第二轮：
left = 1 height[left] = 0 height[right] = 4 leftMax = 3 rightMax = 4因为：
0<4继续结算左边：
ans+=3-0=3left++这表示位置 1 这一列的最终水位是 3，当前柱子高度是 0，所以这一列有 3 格水。
第三轮：
left = 2 height[left] = 2 leftMax = 3结算：
ans+=3-2=1left++第四轮：
left = 3 height[left] = 0 leftMax = 3结算：
ans+=3-0=3left++最终总水量是：
0 + 3 + 1 + 3 = 7整个过程的本质是：
每次确定一列，就把这一列最终能存的水一次性加入答案。13. 下次怎么自己想到并复刻出来
不要直接背代码。建议记住这条推导路线。
第一步，先写出单列公式：
water[i]=min(左边最高柱子,右边最高柱子)-height[i];第二步，想到暴力解法：
每个位置都向左、向右扫描最高柱子。第三步，想到预处理优化：
提前算 leftMax[i] 和 rightMax[i]。第四步，继续优化空间：
不一定要保存所有位置的左右最高值。 只要每次能确定一列，就可以直接加入 ans。第五步，想到双指针：
用 left 和 right 表示当前还没结算的区间。 用 leftMax 和 rightMax 分别维护左右两侧已经见过的最高柱子。第六步，确定移动规则：
哪边当前柱子更矮，哪边就可以先结算。最后得到代码模板：
while(left<right){leftMax=max(leftMax,height[left]);rightMax=max(rightMax,height[right]);if(height[left]<height[right]){ans+=leftMax-height[left];++left;}else{ans+=rightMax-height[right];--right;}}14. 最后总结
这道题最重要的不是记住双指针代码，而是统一计算模型。
不要把它想成：
水从哪里流过来，前面的水能不能当挡板，水要怎么一层一层填。应该把它想成：
每一列最终能有多高的水位。核心公式是：
每列水量=min(左边最高柱子,右边最高柱子)-当前柱子高度双指针只是这个公式的空间优化版本：
从两端向中间走。 动态维护 leftMax 和 rightMax。 哪边当前柱子更矮，就先结算哪边那一列。一句话记忆：
接雨水按列算，短边先结算；左边看 leftMax，右边看 rightMax。
