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