★ FEATURED ARTICLE 我先提个结论“接雨水”这道题是 LeetCode Hot 100 里我刷了十几遍最不亏的一道题。倒不是说它难到天上去而是这题把“怎么从暴力到最优”“怎么识别单调栈场景”“怎么把空间压到O(1)”这三件事全串在了一个模型里。你把这题吃透了单调栈那类题基本等于开了一个口子双指针那个解法更是把“由约束决定移动策略”这种思维焊死在脑子里。难怪它在 Hot 100 里排第 7我猜出题人就是想让每一个刷题的人早点撞上它因为后面一堆题都会用到这里的思想。这篇文章我不打算只是贴个最优解就完事。我会把一个完整的、从一个普通刷题者视角出发的思考过程写出来先怎么暴力想遇到什么瓶颈然后怎么优化成动态规划再发现单调栈更本质最后才发现双指针才是最优雅的那个。每个解法我都给出完整可跑通的代码C 和 Python 双版本、复杂度分析、边界条件还有我实际提交时踩过的坑和心得。1. 题目理解与核心解题思路1.1 题目到底在问什么给你一个非负整数数组height每个元素代表一个宽度为 1 的柱子的高度。把这些柱子画在二维平面里问下过雨后能接多少单位的雨水。这个描述看着简单但真动手时容易在几个点上含糊。我拆开说柱子是实心的宽度固定为 1单位体积的雨水就是“一格”。雨水是自己找平的它不会悬空必须存在一个“低洼处”且左右两侧都有能挡住它的更高柱子。边界上的柱子装不了水哪怕它外侧是无底洞水也会直接流出去。数组元素是非负整数0 也是合法的0 表示那个位置没有柱子。“能接多少雨水”这句话背后的计算单位是每个柱子的列上方的空间能存几格水把这些格数全部加起来。拿一个经典例子来说height [0,1,0,2,1,0,1,3,2,1,2,1]这个例子的答案是 6你手算也能验证索引 2 上方存 1 格索引 4、5、6 这几个位置分别存 1、2、1 格索引 9、10 分别存 1、1 格加起来正好 6。1.2 接水的本质两个方向的约束为什么这题不是简单的“找坑”因为一个位置到底能不能存水、存多少水取决于它左边最高柱子和右边最高柱子之间的“短板”。一个位置i能存的水量写成公式就是water[i] max(0, min(leftMax[i], rightMax[i]) - height[i])其中leftMax[i]表示索引i左边含自身柱子的最高高度rightMax[i]表示索引i右边含自身柱子的最高高度取两者较小值再用这个较小值减去当前位置柱子的高度如果结果是正的说明这个位置能存水如果是负数或 0说明存不了。注意左边或右边没有柱子即当前是边界的情况leftMax或rightMax就等于自身高度那min - height[i] 0天然存不了水。这个公式是整个题目的灵魂。后面所有解法本质上都是在“怎么更快地算出每个位置的 leftMax 和 rightMax”这件事上做文章。1.3 为什么建议先把暴力解想清楚很多人一上来就背最优解但真到了面试或者写题的时候一旦题目变形就抓瞎。我自己的经验是先想暴力再逐步优化这个过程中的每一步都是值的。暴力法就是按公式直接来对于每个位置i分别向左、向右扫描一遍找最大值然后套公式计算。时间复杂度 O(n^2)空间 O(1)。这段代码写出来非常简单但它最大的价值不是性能而是帮我们确认“答案的公式”是对的。当你后面用复杂解法写出结果时可以用暴力解的结果来交叉验证。我在本地写题时就经常把暴力解作为“对照版本”其他解法跑完先跟它比对输出确保没改错逻辑。2. 解法一动态规划前后缀最值2.1 思路演进把重复扫描变成预计算暴力解法慢在哪儿每个位置都要向左右各扫描一遍中间大量重复比较。那自然想到我能不能提前把每个位置的左边最大值和右边最大值都算出来存到数组里之后直接用这不就是动态规划里最经典的前缀/后缀数组技巧嘛。我们分别从左往右、从右往左各扫一遍就把leftMax和rightMax两个数组填满了然后再用公式累加一趟得出答案。时间复杂度O(n)扫了三趟每趟线性空间复杂度O(n)两个辅助数组。2.2 完整代码C 版本class Solution { public: int trap(vectorint height) { int n height.size(); if (n 2) return 0; // 少于3根柱子不可能存水 vectorint leftMax(n), rightMax(n); leftMax[0] height[0]; for (int i 1; i n; i) { leftMax[i] max(leftMax[i - 1], height[i]); } rightMax[n - 1] height[n - 1]; for (int i n - 2; i 0; --i) { rightMax[i] max(rightMax[i 1], height[i]); } int ans 0; for (int i 1; i n - 1; i) { ans max(0, min(leftMax[i], rightMax[i]) - height[i]); } return ans; } };Python 版本class Solution: def trap(self, height: List[int]) - int: n len(height) if n 2: return 0 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[n - 1] height[n - 1] for i in range(n - 2, -1, -1): right_max[i] max(right_max[i 1], height[i]) ans 0 for i in range(1, n - 1): ans max(0, min(left_max[i], right_max[i]) - height[i]) return ans2.3 几个容易栽的细节n 小于等于 2 直接返回 0。这个我一开始老是忽略。想想看0 根柱子不可能装水1 根、2 根也一样水放上去直接流走了所以少于 3 根柱子直接返回 0 是安全的。加了这行不仅省了循环还避免了下标越界的问题。leftMax[i] 包含 height[i] 自身。这里有个概念上的细节我们找的是“左边最高”这个“左边”到底包不包含自己包含。为什么因为公式min(leftMax, rightMax) - height[i]里如果左边界挡板就是自己比如i正好是整个数组的最高点那 leftMax[i] height[i] 减出来是 0逻辑通顺。如果不包含自身那对于边界位置和下降沿就会出错。边界位置i0 和 in-1不需要计算。我们的累加循环是从1到n - 2因为最左边和最右边的柱子外侧没有墙壁水存不住公式必然输出 0所以干脆不参与循环。2.4 动态规划解法怎么看才算真会了我的判断标准你闭上眼能画出 leftMax 和 rightMax 数组在样例上的变化过程并且能解释为什么第一趟从左往右扫、第二趟从右往左扫而不是反过来。这两趟的顺序不是随意的leftMax 依赖左边的结果所以必须从左往右rightMax 依赖右边的结果所以必须从右往左。如果你想挑战一下可以想想二维版本的接雨水怎么解——那个是一个 hard 题LeetCode 407它核心思想其实和这个一维版本一脉相承但用了优先队列。这也能反过来说明一维版本的前缀最值思想有多重要。3. 解法二单调栈更本质的理解3.1 为什么还要学单调栈动态规划解法已经 O(n) 了很多人觉得没必要再学。但我想说单调栈解法在思维层面是另一套东西它不是“每个柱子存多少水”的列视角而是“每一层水是怎么被左右边界夹出来”的行视角。而且单调栈是面试高频考点你不在这道题里学会后面接“柱状图中最大的矩形”LeetCode 84、“每日温度”LeetCode 739、“滑动窗口最大值”里的单调队列思想会更痛苦。接雨水恰恰是最适合入门单调栈的题目之一。3.2 单调栈的核心逻辑维护一个单调递减栈栈底到栈顶是递减的也就是栈顶是最小的栈里存的是柱子的下标不是高度。为什么存下标因为后面计算宽度时需要下标差。遍历每个柱子时如果当前柱子高度小于等于栈顶柱子的高度入栈栈依然满足递减性质如果当前柱子高度大于栈顶柱子的高度说明栈顶这个柱子形成了一个凹槽的底部它左边的柱子栈里下一个元素和当前柱子是它的左右墙壁这时就可以结算积水了。核心计算逻辑h min(height[left], height[right]) - height[bottom] // 水层高度 w right - left - 1 // 水层宽度 ans h * w注意这里算的是一个水平层的水量不是一整列。这一点非常容易混淆。3.3 完整代码C 版本class Solution { public: int trap(vectorint height) { int n height.size(); if (n 2) return 0; int ans 0; stackint st; for (int i 0; i n; i) { while (!st.empty() height[i] height[st.top()]) { int bottom st.top(); st.pop(); if (st.empty()) break; // 左边没有墙存不了水 int left st.top(); int w i - left - 1; int h min(height[left], height[i]) - height[bottom]; ans w * h; } st.push(i); } return ans; } };Python 版本class Solution: def trap(self, height: List[int]) - int: n len(height) if n 2: return 0 ans 0 stack [] for i in range(n): while stack and height[i] height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] w i - left - 1 h min(height[left], height[i]) - height[bottom] ans w * h stack.append(i) return ans3.4 单调栈的细节和坑这里全是实战心得坑一pop 之后要判断栈是否为空。这个是初学者最容易漏的。当bottom出栈后如果栈空说明bottom左边没有任何更高的柱子那么水会从左边界直接流走根本存不起来所以必须break跳出循环而且不能把这个位置入栈或者其实还是要入栈因为当前柱子会成为新的左边界备选。这里的st.push(i)是在 while 循环之外会照常执行。坑二栈里存的是下标比存高度好用。如果只存高度计算宽度时没法确定两个柱子之间隔了多少个单位。所以不管是计算宽度i - left - 1还是判断左墙st.top()都是基于下标的。坑三横向算面积不是纵向。很多人第一次写单调栈解法会写在 while 循环里一层一层地加以为是一次把一列的水都算完。实际上单调栈是遇到一个凸起就结算一层水。你可以把最终结果想象成“横着切出很多层水”每一层都由一个局部的“左墙-坑底-右墙”三元组构成。坑四等于号的处理。当前柱子高度等于栈顶时应该入栈还是不入栈两种做法其实都能得出正确答案但入栈的代码更简洁、更通用。你可以试着想想如果高度相等pop 掉再结算一点水和直接入栈最终总和一样吗答案是一样。因为等高的两个柱子之间没有凹槽不会产生水。但直接入栈能避免不必要的计算所以代码里用的是不是。3.5 单调栈状态模拟我手动模拟一遍看状态变化这样比看代码更直观。假设height [0,1,0,2,1,0,1,3,2,1,2,1]i0栈空push(0)栈[0]i1height[1]1 height[0]0pop(0)栈空breakpush(1)栈[1]i2height[2]0 height[1]1push(2)栈[1,2]i3height[3]2 height[2]0pop(2)栈顶是1left1w1hmin(1,2)-01ans1继续 height[3]2 height[1]1pop(1)栈空breakpush(3)栈[3]i4、5、6……后面读者可以自行推演。每次结算时的三元组(left, bottom, right)就是一层水。你模拟完之后会发现一个很神奇的事一个柱子可能参与多次结算但每次角色不一样。比如柱子 1 高度是 1它既作为 i2 的左墙又作为 i2 的坑底被 pop 掉过。这就是单调栈的魅力元素不是用一次就没了而是在不同阶段扮演不同角色。4. 解法三双指针最优解4.1 本质用两个方向逼近替代预处理数组动态规划解法用了 O(n) 空间存前后缀最大值能不能把空间省掉答案是可以而且算法更简洁。核心思想是我们不需要把每个位置的 leftMax 和 rightMax 都算好只需要知道当前位置的“短板”是谁。如果当前我们已经知道“左侧最大值”比“右侧最大值”小那么对于左侧这个位置来说它的储水量就由左侧最大值决定因为右侧最大值一定大于它。于是我们不用关心右边具体怎么分布直接结算这个位置的储水量然后移动左指针。反之如果右侧最大值比左侧最大值小就结算右侧位置的储水量移动右指针。这个“短板决定结算哪一侧”的思路其实做了一次非常漂亮的剪枝用两个游标代替两个数组。4.2 代码实现C 版本class Solution { public: int trap(vectorint height) { int n height.size(); if (n 2) return 0; int left 0, right n - 1; int leftMax 0, rightMax 0; int ans 0; while (left right) { leftMax max(leftMax, height[left]); rightMax max(rightMax, height[right]); if (leftMax rightMax) { ans leftMax - height[left]; left; } else { ans rightMax - height[right]; --right; } } return ans; } };Python 版本class Solution: def trap(self, height: List[int]) - int: n len(height) if n 2: return 0 left, right 0, n - 1 left_max, right_max 0, 0 ans 0 while left right: left_max max(left_max, height[left]) right_max max(right_max, height[right]) if left_max right_max: ans left_max - height[left] left 1 else: ans right_max - height[right] right - 1 return ans4.3 为什么双指针是对的——从公式角度硬解释这题的双指针我前面讲的思路还只是直觉。你如果想要严谨一点的证明可以这样想对于任意一个位置i如果它在left这一侧被处理说明此刻leftMax rightMax。因为rightMax已经是右侧区间[left1, ...]或者更准确地说是[left, right]中从right往左扫到的最大值而真正的rightMax[i]即位置 i 右侧所有柱子的最大值一定大于等于当前的rightMax所以rightMax[i] rightMax leftMax。于是min(leftMax[i], rightMax[i]) leftMax[i] leftMax。所以ans leftMax - height[left]是准确无误的。反过来如果leftMax rightMax处理右指针时同理min(leftMax[i], rightMax[i]) rightMax。这个证明的意义在于双指针不是“碰巧对了”而是每一步都精确地复现了动态规划公式里的 min 操作。我们只是把“预计算整个数组”变成了“边走边决定每侧谁说了算”。4.4 双指针解法的几个易错点易错点一更新 max 要先于计算水量。leftMax max(leftMax, height[left])必须在计算ans leftMax - height[left]之前完成。不然当前柱子可能就是新的最大值你不更新的话计算出来的水量可能是负数。易错点二等于号归哪边。代码里用的是if (leftMax rightMax)也就是两者相等时走 else 分支处理右指针。其实走哪边结果都一样。你可以试着把条件改成最后答案不会变。因为相等时无论结算左边还是右边都是max - height[i]高的一侧能保证另一侧不缺水结算一侧时另一侧仍然可以作为“靠山”。易错点三while 循环条件left right而不是。这个其实想明白就简单当left right时两个指针指向同一个位置这个位置已经不需要再计算了因为它的两边都扫过了。但如果你不小心写成会导致 left 和 right 同时指向同一个索引然后leftMax和rightMax都包含这一个位置计算出来max - height[i] 0不会影响答案但属于多余的判断。只是left会移动过头可能越界。所以写成是安全且优雅的。4.5 双指针的复杂度时间复杂度O(n)一次线性扫描空间复杂度O(1)只用了几个临时变量。这是这道题的最优解也是我在面试中最推荐的写法。原因不只是省空间而是它把“动规 空间压缩”这件事用一个简单清晰的框架表达了出来现场写不容易错。5. 常见问题与实战经验5.1 刷了几百遍才总结出的避坑清单我把这题所有解法中容易出问题的地方整理成一张表方便随时查阅问题描述原因分析解决方案暴力解法的答案和正确结果对不上忘记了左右边界柱子不能储水循环从 1 到 n-2跳过首尾动态规划解法中 leftMax 计算错误没确认 leftMax 是否包含自身leftMax[i] max(leftMax[i-1], height[i])从 i0 开始单调栈解法提交后结果少 1 或 2pop 后栈空没判断左边没墙还继续结算pop 后立即判断栈空为空则 break单调栈解法超时栈里存了高度而不是下标计算宽度时只能靠计数栈里存下标用i - left - 1计算宽度双指针解法结果偏大左右最大值更新和结算顺序写反了先更新 leftMax/rightMax再计算 ans数组全为递增或递减序列认为会存水实际存水量为 0因为缺少一侧的“墙”数组高度全是 0忘了用非负整数处理直接返回 0不需要额外判断5.2 从这题延伸出来的几个变体变体一柱状图中最大的矩形LeetCode 84。这题正好是“接雨水”的镜像问题。接雨水是找“坑”能装多少水它用单调递增栈而 LeetCode 84 是找“最大矩形面积”用的是单调递减栈。这两题对照着刷是理解单调栈的最佳组合。变体二二维接雨水LeetCode 407。从一维变二维柱子变成了地形网格需要从边界向内做 BFS 优先队列。虽然难度上了个台阶但核心仍然是“边界最矮的墙决定能存多少水”可以说是一维接雨水的思想拓展。变体三每日温度LeetCode 739。这题用单调栈来求“下一个更大元素的距离”跟接雨水的单调栈思想是同一个套路利用栈维护一个单调序列在弹出时结算信息。变体四接雨水 II和二维的区别。三维空间里接水更接近于“多个水箱拼在一起”的思路一般不会出现在面试里但竞赛和 hard 题里见过。5.3 面试环节怎么编排这道题如果你在面试中被问“接雨水”我建议回答顺序不是直接丢最优解而是这样组织体现你的思维过程先说暴力解每个位置找左右最大值O(n^2)。先确认题意和边界。再优化能不能预计算 leftMax/rightMax可以O(n) 时间 O(n) 空间。把动态规划版本写出来。然后提空间优化可以不用两个数组用双指针边走边比较左右最大值O(1) 空间。把双指针写出来。最后可以补充一句还有一个单调栈解法换个视角按层结算也能做到 O(n) 时间 O(n) 空间如果需要我可以展示。这套顺序的好处是展示了你从暴力到最优的完整思维链条。面试官通常不会拦着你反而会觉得你的思路很清晰。如果一开始就直接甩双指针虽然对但容易显得像背题。我自己的经验是面试官最喜欢追问的点是“你为什么在leftMax rightMax时移动左指针”这个问题只要你能用前面 4.3 那个 min 公式的角度去解释基本就稳过。5.4 我在本地测试时常用的几组用例除了 LeetCode 自带的样例我还会用下面这些用例做交叉验证[0,0,0,0,0]全零结果 0[1,0,1]单个凹槽结果 1[1,0,2,0,3]嵌套凹槽结果 1 2 3索引 1 存 1索引 3 存 2[4,2,0,3,2,5]经典混合场景结果 9[5,4,3,2,1]单调递减结果 0[1,2,3,4,5]单调递增结果 0[3,0,0,0,3]一个大坑中间全空结果 9。每组用例我都会用暴力解、动态规划、单调栈、双指针四种方法分别跑一遍确保输出一致。这个方法帮我抓出过很多隐藏 bug比如单调栈版本在[4,2,0,3,2,5]这种多层嵌套场景中最容易算错。5.5 踩坑实录我写单调栈当天差点放弃我第一次写单调栈版本的时候被“到底什么时候结算”绕晕了。我一度以为单调栈解法是“每个凹槽结算一次”结果代码里一行if (st.empty()) break;漏掉了提交后有个用例挂了我以为栈的维护方式错了查了半天。后来我反反复复模拟了几个用例才明白当bottom被弹出去后如果栈空说明它左边没有柱子了水直接流走不产生积水。这行代码不是优化是正确性的必要条件。还有一次我在双指针解法上纠结了很久为什么leftMax rightMax时只能结算左边右边不是还没结算吗后来想通了当前位置的水量只取决于左右最大值中的较小值既然右边最大值已经大于左边最大值了那右边具体是什么根本不重要因为“短板”已经确定了。这个思路一旦理解双指针解法你再也不会忘。5.6 个人总结这题练的是什么能力“接雨水”表面上是一道算法题但它练的是三个层次的思维第一层建模能力把“下雨积水”这种生活场景抽象成数学公式找到每个位置的储水量等于左右最大值的较小值减自身高度。第二层优化意识同样的公式怎么从 O(n^2) 优化到 O(n)再从 O(n) 空间优化到 O(1) 空间。这个过程比答案本身更有价值。第三层工具迁移单调栈不止能解决接雨水还能解决一堆看似不相关的问题。你在这题里打下的基础会在后面遇到“下一个更大元素”“最大矩形”“滑动窗口”等问题时突然派上用场。如果你现在正在刷题而且刷到 Hot 100 前几题我建议你在接雨水这里多停留一会儿把上面四种解法都亲手写一遍模拟几组用例。等你写出双指针并证明它的正确性时你会明显感觉到自己的思维水平上了一个台阶。
阅读完成 · 觉得有帮助？
