力扣hot100刷到第99题“接雨水”这题我前后在面试里见过多次自己也踩过不少坑。它表面是一道数组题实际上把动态规划、双指针、单调栈三个高频考点全串起来了。适合正在刷hot100的算法学习者也适合面试前一晚想快速过一遍经典题的人。这篇文章就围绕这一题把从暴力到最优解的四条路线完整走一遍顺便把最容易写错的地方都标出来。先说结论接雨水的本质是对于每一列它能接住的水量等于左侧最高柱子和右侧最高柱子中较矮的那个减去它自身的高度结果非负才计入。这句话是整道题的题眼后面所有解法都是它的变体。1. 题目到底在问什么先看懂场景再动手1.1 从示例走读题目题目给一个非负整数数组 height每个数字代表宽度为1的柱子高度。下雨之后柱子之间的低洼处会积水问总共能接住多少单位的水。最经典的示例是 height [0,1,0,2,1,0,1,3,2,1,2,1]答案是6。这个示例我建议不要直接看答案自己手动画一遍下标2的柱子高度0它左边最高是下标1的1右边最高是下标3的2所以这一列能接 min(1,2) - 0 1 单位水。下标4的柱子高度1左边最高到2右边最高是下标7的3能接2 - 1 1。下标5高度0左边最高2右边最高3能接2。下标6高度1左边最高2右边最高3能接1。下标8高度2左边最高3右边最高也是3min(3,3) - 2 1。把每个低洼列加起来正好6。这里要特别强调一个容易忽略的点最左边和最右边的柱子永远不可能积水因为水需要左右两边都有边界。所以所有解法里边界位置天然接不到水这也是双指针解法可以把左右端点作为起始哨兵的原因。1.2 两种理解视角按列算与按层算解决这道题有两个完全不同的思考方向。第一个方向是按列计算遍历每一根柱子找它左边最高值和右边最高值用较矮的墙减去自身高度。这个视角贴近直觉也直接对应题目的定义暴力和动态规划都是沿着这个方向展开的。第二个方向是按层计算把水横着切成一层一层的平面每一层只有在左右都有更高的墙时才会被兜住。比如把高度1的那一层单独拎出来看它会被所有高度大于等于1的柱子分割成若干段每一段内部的空隙都是水。这个视角比较反直觉但它是单调栈解法的基础而且在处理二维接雨水、最大矩形这类变体题时按层思考往往更接近问题本质。两种视角的取舍直接决定算法能优化到什么程度。按列视角配合前缀最大值可以做到 O(n)按层视角配合单调栈同样能到 O(n)。如果把两种视角混在一起很容易在写单调栈时想用 leftMax 和 rightMax 去辅助判断结果思路拧巴。建议初学者先选定一个视角吃透再切到另一个视角对比。1.3 约束条件与复杂度基线题目给出的约束是数组长度最多 2 * 10^4高度值最大 10^5。这个数据范围意味着 O(n^2) 的暴力在极端情况下会跑到数量级上亿次操作在力扣上基本会超时但可以用它来验证自己对题意的理解。真正能稳定通过的标准解法要求 O(n) 时间最优方案还需要把额外空间压到 O(1)。还有一个隐含约束height[i] 是非负整数也就是说柱子高度可能为0。高度为0的位置本身不存水但它可以作为低洼地的坑底在按层视角里它是关键的凹槽底部。另外由于所有高度都是整数水量计算结果也一定是整数不会出现浮点数精度问题这让代码调试简单不少。在动手写代码之前先把复杂度目标定下来最优解必须是单层循环 O(n)额外空间能省就省。这样后面写双指针和单调栈时就有了明确方向不会被暴力的写法带偏。2. 四种解法一步步演进从暴力到双指针2.1 暴力解法直接按定义算暴力解法最单纯对每个下标 i从 0 到 i-1 找左边最高从 i1 到 n-1 找右边最高然后计算 min(leftMax, rightMax) - height[i]结果大于0就累加。这个解法代码简单也完全符合题目定义但每个位置都要向两边扫描总复杂度 O(n^2)。我建议即使你已经知道最优解也先把暴力代码写一遍。因为它能帮你确认两件事一是“左侧最高”是否包含自己正确答案是不包含二是边界柱子是否天然无法积水暴力代码里 i 从 1 循环到 n-2 其实就够了。这两个点都是后续优化容易犯错的细节。暴力解法在力扣上通常能通过一部分简单用例但碰到长度为两万的极端数组时就会超时。它的意义在于作为复杂度参照物动态规划和双指针相比它少做了哪部分重复工作答案是重复扫描左右最大值。暴力每次都要重新找最大值而预处理可以让这个查找变成 O(1)。2.2 动态规划用两个数组换时间动态规划的思路是提前把每个位置的左右最大值算好存下来。leftMax[i] 表示从0到i的最大值rightMax[i] 表示从i到n-1的最大值。一次从左到右扫描填充 leftMax一次从右到左扫描填充 rightMax然后第三次遍历累加结果。时间复杂度 O(n)空间复杂度 O(n)。可以跑通的代码长这样def trap(height): 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 ans这里有一个非常坑的语义细节计算下标 i 的水量时leftMax[i] 和 rightMax[i] 都包含了 i 自身的高度。但因为最终公式是 min(leftMax[i], rightMax[i]) - height[i]当 i 本身就是左右最高之一时结果正好为0不会产生错误。这是“包含自身的最大值”也能正确工作的原因不少新手在这里纠结很久。与暴力相比动态规划把“找左右最大”从每次 O(n) 降到了 O(1)这是典型的空间换时间。在面试中写出暴力后紧接着说出这个升级思路是一个很流畅的递进。不过空间 O(n) 还不是终点因为观察发现真正决定答案的并不是全部左右最大值而是两个边界指针动态维护的当前最高。2.3 双指针把空间也省掉双指针是这道题最优雅的解法也是力扣官方题解里推荐的主流方法。它只维护两个变量 leftMax 和 rightMax分别表示左指针扫过的最大高度和右指针扫过的最大高度。左指针从0往右走右指针从 n-1 往左走每次比较 height[left] 和 height[right]结算较矮一边的水量然后移动该指针。为什么可以这样核心逻辑是对于当前位置它的挡板由左右最高中较矮的那个决定而较矮的那一侧一定先被暴露出来。当 height[left] height[right] 时右边至少有一根比当前左指针更高的柱子存在所以左指针位置的水量只取决于 leftMax反之亦然。由于每次只结算较矮的一侧最终每个位置恰好被处理一次不会漏算。这个解法时间 O(n)空间 O(1)在四种解法里是最推荐的答卷。但要注意它虽然代码短面试时反而需要多解释几句为什么较矮侧可以立即结算建议配合画图说明否则面试官容易觉得你在背答案。2.4 单调栈换个角度按层结算单调栈解法不走按列路线而是维护一个高度单调递减的下标栈。遍历到新柱子时只要当前高度大于栈顶高度就说明栈顶位置可能是个凹槽底部需要弹出它并结算一次水量。这个结算不是算一整根柱子的水量而是按层结算左右墙较矮的那个减去凹槽底部高度乘以左右墙之间的宽度。单调栈的时间复杂度同样是 O(n)空间 O(n)。它比双指针难理解但它是理解按层结算的最佳载体也是后续做二维接雨水、最大矩形、行星碰撞等问题的底层工具。如果只是应付接雨水这一题双指针足够如果想把栈类算法题吃透单调栈值得单独花时间。四种解法形成一个完整的递进链条暴力暴露重复计算动态规划用空间消除重复双指针发现连空间都可以省略单调栈则换了一个视角把同一条题眼重新演绎一遍。把这个链条背下来面试从暴力讲到最优解就很自然。3. 实操环节双指针手把手实现与走读3.1 双指针代码逐行拆解直接给一份可以跑通的 Python 实现def trap(height): n len(height) if n 2: return 0 left, right 0, n - 1 left_max, right_max 0, 0 ans 0 while left right: if height[left] height[right]: left_max max(left_max, height[left]) ans left_max - height[left] left 1 else: right_max max(right_max, height[right]) ans right_max - height[right] right - 1 return ans这份代码有几个细节要留意。第一left_max 的更新必须发生在结算之前。如果先执行 ans left_max - height[left] 再更新 left_max那么第一次进入循环时 left_max 还是0会把边界柱子的高度算成水面答案就会偏大。第二循环条件是 left right等于号不能取否则两个指针指向同一个位置时那个位置既不是左墙也不是右墙不应该参与结算。第三分支里用 还是 对最终答案没有影响因为相等高度之间本来就不存水但建议统一写成 保持一致。实际跑一遍示例数组初始 left0, right11。height[0]0 小于 height[11]1进入左分支left_max 更新为0贡献0left 变为1。此时 left1, right11height[1]1 小于等于 height[11]1left_max 更新为1贡献 left_max - height[1] 0left 变为2。继续走下标2结算出1下标3贡献0下标4结算出1下标5结算出2下标6结算出1下标8结算出1最后答案累加为6。整个过程每个位置只走一次逻辑非常顺。3.2 为什么移动较矮的一侧这是双指针解法里最容易被追问的地方。用一个生活化的例子说明想象左右两个人分别站在数组两端手里各拿一个牌子牌子上写着自己一路走来见过的最高柱子。两个人谁脚下的地面更矮谁那边的水位就先被确定因为更矮那边的水位上限已经被自己手里的牌子锁定了。更严格一点说如果右侧全局最大值小于左侧最大值说明全局最高在左侧此时双指针会一直走 else 分支消耗右指针左指针根本轮不到移动。换句话说能走到 height[left] height[right] 这个分支说明右侧至少有足够高的墙存在此时 min(leftMax, rightMax) 的结果由 leftMax 决定。理解到这一层双指针的正确性就真正拿住了。还有一个小技巧面试被问到“为什么不会漏”时可以回答“因为每次结算的是当前较矮侧较矮侧的水量已经被完全确定另一侧哪怕后续出现更高柱子也只影响另一侧不影响已经结算过的位置”。这句话虽然不是完整数学证明但能让面试官知道你是真懂。3.3 三种边界形状的实测我拿三组特殊数据实测过双指针代码。第一组是单调递增数组 [0,1,2,3,4,5]答案一定是0因为水往低处流没有凹槽。模拟时全程走 else 分支right_max 一路更新ans 始终加0符合预期。第二组是单调递减数组 [5,4,3,2,1,0]同样答案是0全程走右分支。第三组是两端高中间低的 [4,2,0,3,5]答案是7。手动算一下下标1能接 min(4,5) - 2 2下标2能接 min(4,5) - 0 4下标3能接 min(4,5) - 3 1总计7。这段代码跑出来同样是7。这三组数据分别验证了无凹槽、单侧高、双侧高三种典型形状建议刷题时把这几个测试用例直接背下来写完代码先跑它们基本能覆盖大部分逻辑错误。另外还有一个边界数组长度是0或1时直接返回0。代码开头那个 if n 2 就是为此准备的如果题目保证最小长度是1这个判断依然安全。4. 单调栈实现的细节与易错点4.1 单调栈的结算逻辑单调栈的模板代码如下def trap(height): stack [] ans 0 n len(height) for i in range(n): while stack and height[i] height[stack[-1]]: top stack.pop() if not stack: break left stack[-1] width i - left - 1 h min(height[i], height[left]) - height[top] ans width * h stack.append(i) return ans这段代码的核心是 while 循环触发条件是当前柱子比栈顶高。栈里维护的是一路走来高度递减的下标所以栈顶就是当前最低的坑底候选。弹出它之后新的栈顶就是它左边最近的、比它高的柱子也就是左墙当前 i 是右墙。左右墙之间的宽度是 i - left - 1意思是左右墙夹着的柱子数量这一段在高度差 h 这一层上全部是水。比较关键的是 popped 之后 break 的逻辑如果弹完栈为空说明这个坑没有左墙左边没有比它更高的柱子那它不可能存水直接跳出 while 去执行 stack.append(i)。这个 break 不是退出整个循环而是跳出当前的 while。4.2 一个关键公式的推导很多博客在写单调栈时直接给出 ans (i - stack[-1] - 1) * (min(height[i], height[stack[-1]]) - height[top])但不说为什么。这里拆开讲一遍。先明确每次 while 弹出的 top 是一个坑底位置它的高度 height[top] 是当前水平面以下的最矮一层。左墙是弹出后新的栈顶 left右墙是当前遍历到的 i。这一层能存的水横向宽度是从 left1 到 i-1 一共 i - left - 1 个格子纵向高度是左右墙较矮的那个减去坑底高度即 min(height[i], height[left]) - height[top]。两者相乘就是这层贡献的水量。为什么只结算这一层而不是所有层因为单调栈保证栈内高度是递减的top 是当前栈里最矮的它上面不可能还有一层更矮的凹槽所以每次弹出最多只结算一层水面。当左右墙更高时后面还会继续弹出并结算更高的层这就是所谓按层结算的含义。示例数组里第一次弹出结算的是高度1的水层第二次弹出结算的是高度2的水层每层贡献叠加就是总水量。4.3 栈里存下标而不是高度写单调栈最容易犯的错是把 height 值直接存进栈里。如果栈里存的是高度数值弹出后想找左墙下标完全找不到宽度没法计算。正确的做法是栈里只存下标需要高度时通过 height[stack[-1]] 去取。另一个容易错的是相等高度的处理。当前高度等于栈顶高度时按 的条件不会触发弹出直接把当前下标入栈。这样栈里会同时存在两个相同高度的下标。对本题来说这不影响答案因为相同高度之间差为0不会结算出正水量。但如果用 触发弹出结算出来的宽度差也不会产生正结果。两种写法都能过建议固定用 语义更清晰。还有一点遍历结束后栈里可能残留一些下标它们都是没有右墙的柱子不需要额外处理。因为接雨水必须有左右墙没右墙的坑要么是递增坡上的柱子要么是栈底边界永远不会贡献正水量。5. 常见问题与排查技巧实录5.1 五个高频报错与原因第一个高频错误是初始化问题。很多人把 left_max 和 right_max 初始化为 height[0] 和 height[n-1]这在双指针里是可以的但必须保证更新顺序正确。还有人在循环里忘记维护 left right 的边界导致死循环或者数组越界。第二个高频错误是把动态规划的左右最大值数组弄反。left_max[i] 要从左往右生成right_max[i] 要从右往左生成生成方向和遍历方向一旦搞反计算结果全是0或者负数。第三个高频错误是单调栈里 while 弹出后 stack 为空时继续用 stack[-1]。代码里需要 break 或 continue 跳过否则会报 IndexError这是我见过最多的运行时错误。第四个高频错误是双指针结算时用了错误的 min。正确写法是结算左指针时只用 left_max不需要写 min(left_max, right_max)因为 right_max 此时还没有扫描到完整的右侧。有人在这里手滑写成 right_max 参与计算结果答案偏小。第五个高频错误是忘记高度差可能为负。暴力解法里如果 min(left_max, right_max) height[i]应该跳过而不是累加负数。用 max(0, ...) 包一下最稳妥。5.2 面试问答加分点如果面试官让你做这道题建议按“暴力到动态规划再到双指针”的顺序讲最后再补一句“其实还能用单调栈思路是按层结算”。先说暴力表示你能拆解问题再优化到双指针展示复杂度意识提单调栈展示知识广度这一套下来基本就稳了。对方如果追问“双指针为什么能省空间”可以说因为每个位置的水量只依赖它左侧最高和右侧最高中较矮的那个而较矮侧一定先被指针确定所以不需要把全部左右最大值存下来。反过来如果题目要求分治或者有修改操作那动态规划预处理两个数组的思路就更有扩展性。还有一个加分细节能说出最左和最右的柱子不能积水因为缺少边界。这个点很多人想不到但它是所有解法的共同前提随口提一句会让面试观感好很多。5.3 相关变式题怎么串起来接雨水在算法题里不是孤立的。把数组换成二维矩阵就变成二维接雨水需要优先队列加广度优先遍历把求水量换成求最大矩形面积就是柱状图中最大的矩形单调栈的结算方向正好反过来一个算凹槽一个算凸起如果把柱子换成可以任意调节高度的容器就变成装水类问题。核心都是“边界挡板加单调性”这两个词。我自己刷到后面发现接雨水更像是单调栈的入门课。把这道题吃透再去写柱状图中最大的矩形会有一种“原来反过来写就行”的顿悟感。所以如果你时间有限单刷这一题至少要把双指针和单调栈两种解法都写一遍比刷十道同类型简单题更划算。最后再分享一个实战习惯刷完这道题后我把示例数组复制到本地脚本里分别用双指针、动态规划、单调栈三份实现跑同一个用例打印每一步的 ans 变化对照着看差别。这个方法帮我确认了三种解法的结算方式确实是同一种答案的三种切法。你也试试比盯着代码发呆有效得多。