1. 问题背景与核心思路第一次看到盛最多雨水这个问题时我正坐在杭州西湖边的长椅上。看着湖面上泛起的涟漪突然想到如果这些涟漪是容器壁那最多能接住多少雨水呢这个看似简单的几何问题实际上蕴含着巧妙的算法思想。给定n个非负整数表示的高度图每个柱子的宽度为1计算下雨后这个排列能接多少雨水。比如输入[0,1,0,2,1,0,1,3,2,1,2,1]输出应该是6。这个问题的经典解法之一就是双指针法——用两个指针从数组两端向中间移动在O(n)时间复杂度和O(1)空间复杂度内解决问题。2. 双指针解法详解2.1 基本思路解析双指针法的核心在于对于任意一个柱子它能接的雨水量取决于它左右两边最高柱子中的较小值短板效应减去它自身的高度。具体来说初始化左指针left0右指针rightheight.length-1维护左右两边的当前最大值left_max和right_max比较height[left]和height[right]如果height[left] height[right]如果height[left] left_max更新left_max否则累加left_max - height[left]到结果left右移否则类似处理右指针的情况2.2 完整代码实现def trap(height): if not height: return 0 left, right 0, len(height) - 1 left_max right_max 0 res 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: res left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: res right_max - height[right] right - 1 return res关键点每次移动较矮那边的指针因为积水高度是由较矮的一边决定的。这就是双指针法的精妙之处。3. 算法正确性证明3.1 为什么移动较矮的指针假设height[left] height[right]此时left_max right_max因为right_max已经包含了height[right]所以当前left位置的积水量由left_max决定即使右边有更高的柱子left位置的水也不会超过left_max反之亦然。这就保证了我们每次都能正确计算当前指针位置的积水量。3.2 时间复杂度分析双指针法只需要遍历数组一次left和right指针总共移动n次因此时间复杂度是O(n)。我们只使用了常数个额外变量空间复杂度是O(1)。4. 实际应用与变种4.1 真实场景应用这个问题看似简单但在实际中有重要应用城市规划中的雨水收集系统设计地形分析中的蓄水能力计算图像处理中的轮廓分析4.2 常见变种问题三维接雨水问题将问题扩展到二维高度图容器最多水问题求两个柱子组成的容器能装最多水带障碍物的接雨水某些柱子不能蓄水5. 性能优化与边界情况5.1 优化技巧提前终止当left_max max(height)时可以提前终止预处理最大值先找出全局最大值分成左右两部分处理5.2 边界情况处理# 特殊情况的处理 if len(height) 3: # 至少需要3根柱子才能积水 return 0 if sum(height) 0: # 所有高度为0 return 06. 与其他解法的对比6.1 动态规划法动态规划需要O(n)空间存储每个位置的左右最大值虽然也是O(n)时间复杂度但空间效率不如双指针。# DP解法示例 def trap_dp(height): n len(height) left_max [0]*n right_max [0]*n left_max[0] height[0] for i in range(1,n): left_max[i] max(left_max[i-1], height[i]) right_max[-1] height[-1] for i in range(n-2,-1,-1): right_max[i] max(right_max[i1], height[i]) return sum(min(left_max[i],right_max[i])-height[i] for i in range(n))6.2 单调栈解法单调栈解法可以找出每个柱子左右第一个比它高的柱子适合某些变种问题但实现起来更复杂。7. 常见错误与调试技巧7.1 新手常见错误指针移动条件写反应该移动较矮的指针忘记更新left_max或right_max边界条件处理不全如空数组或全0数组7.2 调试建议可视化调试很有帮助打印每次循环时的指针位置和当前计算结果绘制高度图和指针移动过程对小例子手动模拟算法执行过程8. 扩展思考8.1 为什么双指针法有效本质上是因为我们利用了问题的对称性。积水的高度总是由较矮的一边决定所以可以安全地移动较矮的指针而不用担心错过更大的积水可能性。8.2 实际工程中的应用在实际工程项目中我经常用类似的思路解决资源分配问题。比如在分布式系统中平衡两个节点的负载或者在UI布局中计算自适应容器的尺寸。这种双指针的思想远比这个算法本身更有价值。 
长河君 · 2026/11/3 4:22:06 · 阅读 1.2k 双指针法解决盛最多雨水问题详解
1. 问题背景与核心思路第一次看到盛最多雨水这个问题时我正坐在杭州西湖边的长椅上。看着湖面上泛起的涟漪突然想到如果这些涟漪是容器壁那最多能接住多少雨水呢这个看似简单的几何问题实际上蕴含着巧妙的算法思想。给定n个非负整数表示的高度图每个柱子的宽度为1计算下雨后这个排列能接多少雨水。比如输入[0,1,0,2,1,0,1,3,2,1,2,1]输出应该是6。这个问题的经典解法之一就是双指针法——用两个指针从数组两端向中间移动在O(n)时间复杂度和O(1)空间复杂度内解决问题。2. 双指针解法详解2.1 基本思路解析双指针法的核心在于对于任意一个柱子它能接的雨水量取决于它左右两边最高柱子中的较小值短板效应减去它自身的高度。具体来说初始化左指针left0右指针rightheight.length-1维护左右两边的当前最大值left_max和right_max比较height[left]和height[right]如果height[left] height[right]如果height[left] left_max更新left_max否则累加left_max - height[left]到结果left右移否则类似处理右指针的情况2.2 完整代码实现def trap(height): if not height: return 0 left, right 0, len(height) - 1 left_max right_max 0 res 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: res left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: res right_max - height[right] right - 1 return res关键点每次移动较矮那边的指针因为积水高度是由较矮的一边决定的。这就是双指针法的精妙之处。3. 算法正确性证明3.1 为什么移动较矮的指针假设height[left] height[right]此时left_max right_max因为right_max已经包含了height[right]所以当前left位置的积水量由left_max决定即使右边有更高的柱子left位置的水也不会超过left_max反之亦然。这就保证了我们每次都能正确计算当前指针位置的积水量。3.2 时间复杂度分析双指针法只需要遍历数组一次left和right指针总共移动n次因此时间复杂度是O(n)。我们只使用了常数个额外变量空间复杂度是O(1)。4. 实际应用与变种4.1 真实场景应用这个问题看似简单但在实际中有重要应用城市规划中的雨水收集系统设计地形分析中的蓄水能力计算图像处理中的轮廓分析4.2 常见变种问题三维接雨水问题将问题扩展到二维高度图容器最多水问题求两个柱子组成的容器能装最多水带障碍物的接雨水某些柱子不能蓄水5. 性能优化与边界情况5.1 优化技巧提前终止当left_max max(height)时可以提前终止预处理最大值先找出全局最大值分成左右两部分处理5.2 边界情况处理# 特殊情况的处理 if len(height) 3: # 至少需要3根柱子才能积水 return 0 if sum(height) 0: # 所有高度为0 return 06. 与其他解法的对比6.1 动态规划法动态规划需要O(n)空间存储每个位置的左右最大值虽然也是O(n)时间复杂度但空间效率不如双指针。# DP解法示例 def trap_dp(height): n len(height) left_max [0]*n right_max [0]*n left_max[0] height[0] for i in range(1,n): left_max[i] max(left_max[i-1], height[i]) right_max[-1] height[-1] for i in range(n-2,-1,-1): right_max[i] max(right_max[i1], height[i]) return sum(min(left_max[i],right_max[i])-height[i] for i in range(n))6.2 单调栈解法单调栈解法可以找出每个柱子左右第一个比它高的柱子适合某些变种问题但实现起来更复杂。7. 常见错误与调试技巧7.1 新手常见错误指针移动条件写反应该移动较矮的指针忘记更新left_max或right_max边界条件处理不全如空数组或全0数组7.2 调试建议可视化调试很有帮助打印每次循环时的指针位置和当前计算结果绘制高度图和指针移动过程对小例子手动模拟算法执行过程8. 扩展思考8.1 为什么双指针法有效本质上是因为我们利用了问题的对称性。积水的高度总是由较矮的一边决定所以可以安全地移动较矮的指针而不用担心错过更大的积水可能性。8.2 实际工程中的应用在实际工程项目中我经常用类似的思路解决资源分配问题。比如在分布式系统中平衡两个节点的负载或者在UI布局中计算自适应容器的尺寸。这种双指针的思想远比这个算法本身更有价值。