leetcode 题解之 42. 接雨水Trapping Rain Water双数组、双指针与单调栈全方位剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以本仓库的 42. 接雨水题解 为主体系统讲解 LeetCode 42 题「Trapping Rain Water」从暴力枚举到双数组、再到双指针的完整推导链并补充前置知识中提到的单调栈解法。读完本文你将掌握接雨水问题的数学模型h[i] min(leftMax, rightMax)、空间换时间与双指针优化的本质以及如何将其迁移到 84. 柱状图中最大的矩形 等同类问题中。题目描述与问题建模给定n个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 示例: 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6本题难度为hard题目地址为 https://leetcode-cn.com/problems/trapping-rain-water/。核心难点在于柱子的高度参差不齐如何确定每个位置“盛水的高度上限”。暴力思路与核心建模如果采用暴力求解思路应该是枚举每一个位置i下雨后的积水量累加记为答案for (let i 0; i height.length; i) { area (h[i] - height[i]) * 1; // h为下雨之后的水位 }问题随之转化为求h数组——即每个位置下雨之后的水位。这里h[i]其实等于左右两侧柱子的最大值中的较小值h[i] Math.min(左边柱子最大值, 右边柱子最大值)这个公式是整个问题的灵魂一个位置能不能积水、能积多少水取决于两侧“围墙”中较矮的那一堵。以上图为例h数组为[0, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 1]逐项与柱高[0,1,0,2,1,0,1,3,2,1,2,1]相减即可得到总积水 6 个单位。因此问题的关键在于求解左边柱子最大值和右边柱子最大值。前置知识本仓库的题解文档在开始前点明了三道必备的知识储备也是后续三种解法的底层支撑空间换时间用两个数组提前算出每个位置的左右最大值把每次询问的 $O(N)$ 扫描降到 $O(1)$ 查表双指针在两侧同时收缩用常数变量替代完整数组把空间复杂度从 $O(N)$ 压到 $O(1)$单调栈维护一个单调递减的栈在一次遍历中找到每个位置的左右“边界”可用于流式处理高度图。双数组解法空间换时间思路我们其实可以用两个数组来表示leftMax、rightMax。以leftMax为例leftMax[i]代表 i 的左侧柱子的最大值因此我们维护两个数组即可从左向右扫一遍得到每个位置的左侧最大值leftMax含当前位置自身从右向左扫一遍得到每个位置的右侧最大值rightMax含当前位置自身逐位置累加Math.min(leftMax[i], rightMax[i]) - height[i]即为答案。关键点解析建模h[i] Math.min(左边柱子最大值, 右边柱子最大值)h 为下雨之后的水位。代码代码支持 JS、Python3、CJS Code/* * lc appleetcode id42 langjavascript * * [42] Trapping Rain Water * */ /** * param {number[]} height * return {number} */ var trap function (height) { let max 0; let volume 0; const leftMax []; const rightMax []; for (let i 0; i height.length; i) { leftMax[i] max Math.max(height[i], max); } max 0; for (let i height.length - 1; i 0; i--) { rightMax[i] max Math.max(height[i], max); } for (let i 0; i height.length; i) { volume volume Math.min(leftMax[i], rightMax[i]) - height[i]; } return volume; };Python Codeclass Solution: def trap(self, heights: List[int]) - int: n len(heights) l, r [0] * n, [0] * n ans 0 for i in range(1, len(heights)): l[i] max(l[i - 1], heights[i - 1]) for i in range(len(heights) - 2, 0, -1): r[i] max(r[i 1], heights[i 1]) for i in range(len(heights)): ans max(0, min(l[i], r[i]) - heights[i]) return ans注意此处 Python 版l[i]维护的是i左侧不含自身的最大值r[i]维护的是i右侧不含自身的最大值因此累加时使用了max(0, ...)兜底避免出现负数。C Codeint trap(vectorint heights) { if(heights.size() 3) return 0; int ans 0; int size heights.size(); vectorint left_max(size), right_max(size); left_max[0] heights[0]; for (int i 1; i size; i) { left_max[i] max(heights[i], left_max[i - 1]); } right_max[size - 1] heights[size - 1]; for (int i size - 2; i 0; i--) { right_max[i] max(heights[i], right_max[i 1]); } for (int i 1; i size - 1; i) { ans min(left_max[i], right_max[i]) - heights[i]; } return ans; }说明C 版本的遍历区间为[1, size - 2]因为首尾柱子天然无法积水同时原文档中heights null的写法在 C 中不合法此处已改为对size 3的边界处理保证代码可直接编译运行。复杂度分析时间复杂度$O(N)$三次线性遍历空间复杂度$O(N)$两个长度与柱高数组相同的辅助数组。双指针解法把空间压到 O(1)这种解法为进阶解法大家可以视自身情况掌握。思路上面代码比较好理解但是需要额外的 N 的空间。从上面解法可以看出我们实际上只关心左右两侧较小的那一个并不需要两者都计算出来。具体来说如果l[i 1] r[i]那么最终积水的高度由 i 的左侧最大值决定如果l[i 1] r[i]那么最终积水的高度由 i 的右侧最大值决定。因此我们不必维护完整的两个数组而是可以只进行一次遍历同时维护左侧最大值和右侧最大值使用常数变量完成即可。这是一个典型的双指针问题。具体算法维护两个指针left和right分别指向头尾。初始化左侧和右侧最高的高度都为 0。比较height[left]和height[right]3.1 如果height[left] height[right]那么瓶颈在于height[left]不需要考虑height[right]3.1.1 如果height[left] left_max则当前格子积水面积为(left_max - height[left])否则无法积水即积水面积为 0也可将逻辑统一为盛水量为max(0, left_max - height[left])3.1.2 左指针右移一位左指针位置的雨水量已经计算完成移动到下个位置用同样的方法计算。3.2 否则瓶颈在于height[right]不需要考虑height[left]3.2.1 如果height[right] right_max则当前格子积水面积为(right_max - height[right])否则无法积水即积水面积为 0也可将逻辑统一为盛水量为max(0, right_max - height[right])3.2.2 右指针左移一位。为什么“矮的一侧可以直接结算”因为水位被矮侧封顶矮侧那边即使有更高的柱子也无法抬高当前位置的水位。这本质上就是h[i] min(leftMax, rightMax)在指针移动过程中的增量式维护。代码代码支持 Python、C、Go、PHPPython Codeclass Solution: def trap(self, heights: List[int]) - int: n len(heights) l_max r_max 0 l, r 0, n - 1 ans 0 while l r: if heights[l] heights[r]: if heights[l] l_max: ans l_max - heights[l] else: l_max heights[l] l 1 else: if heights[r] r_max: ans r_max - heights[r] else: r_max heights[r] r - 1 return ansC Codeclass Solution { public: int trap(vectorint heights) { int left 0, right heights.size() - 1; int ans 0; int left_max 0, right_max 0; while (left right) { if (heights[left] heights[right]) { heights[left] left_max ? (left_max heights[left]) : ans (left_max - heights[left]); left; } else { heights[right] right_max ? (right_max heights[right]) : ans (right_max - heights[right]); --right; } } return ans; } };Go Codefunc trap(height []int) int { if len(height) 0 { return 0 } l, r : 0, len(height)-1 lMax, rMax : height[l], height[r] ans : 0 for l r { if height[l] height[r] { if height[l] lMax { ans lMax - height[l] } else { lMax height[l] } l } else { if height[r] rMax { ans rMax - height[r] } else { rMax height[r] } r-- } } return ans }PHP Codeclass Solution { /** * param Integer[] $height * return Integer */ function trap($height) { $n count($height); if (!$n) return 0; $l 0; $l_max $height[$l]; $r $n - 1; $r_max $height[$r]; $ans 0; while ($l $r) { if ($height[$l] $height[$r]) { if ($height[$l] $l_max) $ans $l_max - $height[$l]; else $l_max $height[$l]; $l; } else { if ($height[$r] $r_max) $ans $r_max - $height[$r]; else $r_max $height[$r]; $r--; } } return $ans; } }复杂度分析时间复杂度$O(N)$单次遍历空间复杂度$O(1)$仅使用常数个变量。扩展单调栈解法呼应前置知识题解文档的前置知识中明确提到了单调栈。接雨水同样可以用单调栈在一次遍历中完成维护一个单调递减栈栈内柱高从底到顶递减当遍历到一根比栈顶更高的柱子时说明栈顶元素找到了它的“右边界”此时栈顶弹出的位置就是一个可以盛水的“凹槽”弹栈得到凹槽底部bottom height[stack.pop()]新的栈顶是凹槽的左边界若栈为空则说明左侧无墙无法积水凹槽宽度为right - left - 1水位为min(左墙高, 右墙高) - bottom累加(min(height[stack.peek()], height[i]) - bottom) * (i - stack.peek() - 1)即为该凹槽的积水量。由于每个元素最多入栈、出栈各一次该解法的时间复杂度为 $O(N)$空间复杂度为 $O(N)$。如果对单调栈的维护细节哨兵技巧、边界处理还不熟悉可以参考本仓库 84. 柱状图中最大的矩形 题解中的单调栈Accepted一节它用“首尾加哨兵、保证所有柱子出栈”的方式统一了边界逻辑单调栈的应用模式也可以进一步查阅仓库的 单调栈专题。三种解法对比与选型建议解法核心思想时间复杂度空间复杂度适用场景双数组空间换时间预处理左右最大值$O(N)$$O(N)$思路最直观适合作为第一版解法数据量很大时需注意内存双指针只关心较矮一侧常数变量维护$O(N)$$O(1)$面试最优解空间敏感场景首选单调栈弹栈结算凹槽一次遍历$O(N)$$O(N)$流式输入无法预知数组长度或需要同时定位左右边界时实际面试中推荐按“暴力建模 → 双数组 → 双指针”的顺序层层递进讲解最后用复杂度分析收尾既展示推导能力又展示优化意识。相关题目84. largest-rectangle-in-histogram同为柱状图类问题核心是求“左右第一个比 i 小”的位置与接雨水的单调栈思路互为镜像一个是求比当前大的边界积水一个是求比当前小的边界求面积仓库中 two-pointers 专题 汇集了双指针类题目的分类总结可用于巩固本文的双指针技巧本仓库每日一题板块daily 目录持续收录了各类题目的图解与证明可作为刷题路线的延伸参考。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考