刷 LeetCode 的朋友应该都有过这种体验一道题看题解秒懂关上页面自己写却卡住。42. 接雨水就是我心中“看懂了但写不出来”的典型代表——我前前后后刷过三遍第一遍背代码第二遍理解公式第三遍才敢说自己真正想明白了。这道题最折磨人的地方在于它不是考你某个冷门 API也不是考复杂的数学推导而是考你有没有建立一套“从物理直觉到算法抽象”的思维链路每个格子到底能存多少水哪些信息必须提前知道哪些信息可以边走边算LeetCode 热题 100 里接雨水稳稳站在“高频中的高频”那一档。不是因为题目本身多难而是因为它像一面镜子暴力法暴露你的建模能力动态规划考察你的空间换时间意识单调栈检验你对“边界结算”的理解双指针则直接反映你能不能看穿最优解背后的不变式。面试官太爱拿它做“思维过程”观察了所以这篇文章我不想再复述一遍标准题解而是按一条完整的探究链路来拆从最笨的暴力开始逐步压缩时间和空间最后落到双指针那个让人拍大腿的解法上。你把这篇文章吃透不光这道题通了靠“左右边界制约”解的一类题也基本通了。1. 为什么几乎所有公司都爱考这道“破柱子”题先聊点题外话。接雨水的题干非常简单给你 n 个非负整数表示宽度为 1 的柱子的高度图计算下雨之后能接多少雨水。输入[0,1,0,2,1,0,1,3,2,1,2,1]输出 6。没了。但就是这个场景能同时撬动好几层能力的考察。第一层是问题建模。很多人一上来就把“能接多少水”等价成“找凹槽面积”然后开始扫描局部极小值——这是个典型的直觉陷阱。柱子之间能存水不是看局部有没有凹陷而是看每个位置左右两边有没有更高的“墙”。建模建错了后面全错。第二层是复杂度意识。暴力解法谁都能写但O(n²)在 n 达到 10^5 或者 2×10^4 的时候直接超时。面试官会追问“能不能优化”这就逼着你从“每个位置现找左右最大”过渡到“提前算好左右最大”。到这一步你其实已经写出了动态规划解法。第三层才是真正的分水岭空间能不能再压缩遍历方向能不能反过来当你能回答“双指针为什么可以边走边结算”你才算真正理解了这题的物理过程而不是背了一个模板。我经常把这道题比作“算法思维的分级体检”暴力法是及格线动态规划是平均水平单调栈说明你见过套路双指针则代表你理解了问题本质。这也是为什么从字节到微软从实习到社招它出现的频率高得离谱。别再问“这题有什么实际应用”了它最大的应用场景就是帮面试官在两轮对话内看清你的算法底子。2. 先搞清楚每一列能存多少水核心公式的推导解题的第一步永远不是写代码而是把“水怎么存”这件事用公式表达出来。这一节我们不谈任何技巧就做一件事把每个柱子上方能接的水量算清楚。2.1 木桶效应在这里的正确打开方式大家都听过“木桶能装多少水取决于最短的那块板”但接雨水这道题里每个格子不是跟全局最矮的柱子比而是跟它左侧最高柱和右侧最高柱分别比。为什么因为水是“局部围住”的某个位置上方能不能存水只取决于它左边有没有柱子挡住、右边有没有柱子挡住以及这两堵墙谁更矮。如果左右两侧任意一侧没有比当前柱子更高的那这个位置存不住水。如果两侧都有更高的柱子那这个位置的水面高度会被较矮的那一侧限制住水位等于min(左侧最高, 右侧最高)。当前柱子的高度本身会占掉一部分空间所以真正能存的水是“限制水位”减去“当前柱高”负数按 0 处理。这就是全题唯一的公式water[i] max(0, min(leftMax[i], rightMax[i]) - height[i])2.2 为什么不能直接跟全局最高柱比假设输入是[3, 0, 0, 2, 0, 4]。全局最高是 4。位置 1 的左侧最高是 3右侧最高是 4水位被 3 限制存水量是 3。位置 3 的左侧最高是 3右侧最高是 4水位也是 3减去自身高度 2存 1。这两个位置都说得通因为它们右侧确实有 4 这个“高墙”。但如果输入变成[5, 0, 0, 2, 0, 3]全局最高是 5。位置 5高度 3的右侧没有比它更高的柱子了它存不了水。可如果简单跟全局最高 5 比min(5, 5) - 3 2那就算错了。所以每个位置都必须看“自己左侧的最大值”和“自己右侧的最大值”而不是全局最大值。或者换个说法右侧最高只考虑当前柱子右边那一段未来不可见。2.3 暴力解法的意义先写对再写快基于这个公式最直接的暴力解法就是遍历每个位置向左扫一遍找最大值向右扫一遍找最大值然后套公式累加。def trap_brute_force(height): n len(height) ans 0 for i in range(n): left_max 0 for j in range(i, -1, -1): left_max max(left_max, height[j]) right_max 0 for j in range(i, n): right_max max(right_max, height[j]) ans max(0, min(left_max, right_max) - height[i]) return ans这个写法没有任何技巧但它有两个不可替代的价值它是后续所有解法的“验证基准”。我调试单调栈和双指针时都是拿这个暴力结果做对拍的——左右区间随机生成几千组数据输出不一致就是代码有 bug。它帮你把“每个位置的水量”这个概念钉死在心里。后续的解法无论多花哨都是在优化left_max和right_max的获取方式而不是在改变这个公式。复杂度就不多说了时间O(n²)空间O(1)。leetcode 上一跑n 稍微大一点就超时但这种“先能算对再追求效率”的思路反而是我建议所有刷题新手养成的习惯。3. 用预处理换时间动态规划解法里藏着的通用思想暴力法慢在哪儿每个位置都要重新向左、向右扫描一遍而且大量扫描是重复的。位置 i 和位置 i1 的左侧最大值之间明明只差一个height[i1]的比较暴力法却把前面所有柱子重新扫了一遍。这种“重复计算”就是优化的信号。3.1 前缀最大与后缀最大数组的构造动态规划解法做了一件非常朴素的事把每个位置的左右最大值提前算好存进数组。左边最大值数组leftMax[i]表示height[0..i]的最大值右边最大值数组rightMax[i]表示height[i..n-1]的最大值。def trap_dp(height): n len(height) if n 0: return 0 left_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 [0] * n 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(n): ans max(0, min(left_max[i], right_max[i]) - height[i]) return ans两个数组的递推关系就是标准的“前缀最值”和“后缀最值”left_max[i]只依赖left_max[i-1]和height[i]right_max[i]只依赖right_max[i1]和height[i]。这就是动态规划里的“无后效性”——当前状态只由前置状态决定不需要回退重算。时间降到了O(n)代价是O(n)的额外空间。很多第一次接触这个解法的朋友会困惑“这不是空间换时间吗面试官会不会觉得不够优”如果面试官不追问这个答案已经合格了。但如果你能主动补一句“空间上还能优化到 O(1)”印象分会明显不一样。这正是接雨水这道题精妙的地方它逼着你把“能用数组存”进化到“连数组都省掉”。3.2 这类“预处理数组”思路在热题里的普适性接雨水不是唯一需要前缀/后缀信息的题。LeetCode 热题 100 里有好几道都是同一个套路我整理一下你对照着看会非常有感觉题目预处理思路和接雨水的关联238. 除自身以外数组的乘积前缀积 后缀积同样是先预处理“左右两侧信息”再按位置合并739. 每日温度从右往左遍历配合栈或数组记录后缀信息的递推和 right_max 的构造思路一致84. 柱状图中最大的矩形单调栈找左右边界和接雨水的单调栈解法互为镜像一个是围水一个是扩矩形说白了很多题目表面上千变万化底层都是在问同一件事每个位置能不能用 O(1) 时间拿到“左侧某种极值/累计值”和“右侧某种极值/累计值”。脑子里装着这个框架下次遇到“每个元素要跟左右比较”的题第一反应就不再是“怎么遍历”而是“能不能预处理”。当然空间 O(n) 也留下了优化空间——接雨水的最优解就是把这两个数组变成两个变量。4. 单调栈换一种视角从“按列算”到“按层结算”如果说动规解法的思维是“站在每一列上方看它能存多少水”那单调栈解法的思维就是“站在水面上看每一层水是被哪两根柱子围出来的”。这是两种完全不同的建模方式也是很多人第一次接触时最懵的地方。4.1 单调栈到底在维护什么先说结论我们维护一个从栈底到栈顶高度单调递减的下标栈。遍历每个柱子时只要当前柱子高度小于等于栈顶柱子高度就把它压进栈里——相当于“当前还没有找到比它更高的右墙”。一旦当前柱子的高度大于栈顶柱子的高度说明栈顶这根柱子的“右墙”出现了可以结算它作为坑底时能存的水。这里的关键是出栈的栈顶元素是“坑底”新的栈顶元素是“左墙”当前遍历到的元素是“右墙”。水的深度等于min(左墙高, 右墙高) - 坑底高水的宽度等于右墙下标 - 左墙下标 - 1。注意这里的宽度是“坑底位置到左墙之间”的水平距离这就是为什么这种视角叫“按层结算”。用代码说话def trap_stack(height): stack [] ans 0 n len(height) for i in range(n): while stack and height[i] height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] width i - left - 1 depth min(height[left], height[i]) - height[bottom] ans width * depth stack.append(i) return ansbreak那个分支很关键如果弹出坑底后栈空了说明左边没有更高的墙这次无法形成水坑直接跳出循环把当前柱子压入栈中。这不是边界情况而是常见的空栈场景——比如数组一开始是递减的前两根柱子之间根本存不了水。4.2 手动推演一个例子拿题目自带的[0,1,0,2,1,0,1,3,2,1,2,1]来走前几步i0栈空压入 0。i1height[1]1 height[0]0弹出 0 作为坑底栈空无左墙不结算。压入 1。i2height[2]0 height[1]1压入 2。此时栈底到栈顶为 [1, 2]高度 [1, 0]。i3height[3]2 height[2]0弹出 2 作为坑底左墙是栈顶 1右墙是当前 3。width3-1-11depthmin(1,2)-01ans 加 1。栈变成 [1]height[3]2 仍然大于 height[1]1再弹出 1栈空无左墙不结算。压入 3。这一步恰好就是教科书里的“第一个水坑”下标 2 的位置被高度 1 的柱子下标1和高度 2 的柱子下标3围住存了 1 单位水。继续往下走你会发现单调栈结算的不是一个完整的大凹槽而是“一层一层”地结算。下标 4 到 6 那个小坑以及后面更大的坑都是在遍历过程中逐步按层累加的。这也是它和动规解法最大的差异动规站在列的视角水是竖向一块一块累计的单调栈站在行的视角水是横向一层一层累计的。4.3 什么时候该想到单调栈很多读者问过我“我知道单调栈这个数据结构但怎么判断一道题该用它”我的经验就三条题目里出现“找左边/右边第一个比当前元素大或小的元素”这类描述这基本是单调栈的正面信号。计算某个区间内的“围成面积”“水量”“最大矩形”时如果这个量的定义和“两侧边界的高度/位置”强相关单调栈往往能直接把边界维护在栈里。你已经写出了一个 n² 或需要反复寻边的解法且遍历方向与边界判断相关时可以主动往单调栈上靠一靠。接雨水恰好在第 2 条和第 3 条的交汇处。84. 柱状图中最大的矩形也是这两个条件都满足的一道题你可以把两题放一起对比着做。顺便提醒一句接雨水的单调栈维护的是“递减栈”84 题维护的是“递增栈”两者恰好相反千万别背反。5. 双指针从 O(n) 空间到 O(1) 空间的临门一脚到了这一节我们要解决最后一个问题两个预处理数组能不能省略答案是能而且省略的方式一不小心就会绕晕人。先说结论双指针解法不是动规的简单压缩它背后站着一个非常强的“位置结算不变式”。5.1 为什么左右指针敢边走边算双指针解法的代码极其简洁def trap_two_pointers(height): left, right 0, len(height) - 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 height[left] height[right]: ans left_max - height[left] left 1 else: ans right_max - height[right] right - 1 return ans很多第一次看到这个写法的人都会问处理height[left] height[right]的左边分支时right_max明明只是“右边已经扫描过的最大值”右边还没走完怎么能确定左边位置的水量答案是这个位置的接水量根本不需要知道右边完整的信息。我们用一个生活化的场景来解释。假设你站在一排柱子中间左边最高的柱子已经确定是 5 米右边你目前看到最高的柱子是 7 米而且你正站在一根 3 米的柱子旁边。这时问你脚下这根 3 米柱子能存多少水你会说水位最高到 5 米存 2 米。为什么右边后面可能还有 100 米的柱子也不影响因为水面高度取的是左右最大值的较小者左边封顶 5 米右边就算出现更高的min(左边最大, 右边最大)也不会超过 5 米。反过来如果左边最大值是 5 米右边目前只看到 3 米那右边这根柱子的水量也已经被右边的 3 米封顶了吗不是因为左边已经确定有 5 米了右边一旦后续出现更高的柱子水位会上涨。所以这时不能结算右边柱子反而应该继续移动右指针去“探测”右边更高的可能性。当右边 max 小于等于左边 max 时右边的水量才稳定。双指针的循环就是这样每次比较height[left]和height[right]的大小小的那一侧它的接水量已经由当前维护的left_max和right_max的较小者决定了可以直接结算并移动指针大的一侧暂时不结算因为它可能还有“更好的右墙”没探到。这个思路本质上就是“哪边更矮就先处理哪边因为矮的那边已经不可能被更高的墙改变了”。5.2 边界条件与常见误区双指针代码虽然短但有几个地方特别容易出岔子初始化时left_max和right_max必须先更新再算水。我第一次写的时候把left_max max(left_max, height[left])放到了结算之后结果第一个位置直接出现负数。先更新是为了保证当前柱子的高度已经纳入“墙”的候选否则你结算的是“还没看过当前位置”时的信息。循环条件是left right不是left right。当左右指针相遇时中间只剩一堵墙不可能再接水所以不用处理。结算时用的是left_max - height[left]而不是min(left_max, right_max) - height[left]。因为在这个分支里left_max right_max一定成立否则会走 else所以min就是left_max。同理else 分支里用right_max。这里直接套公式也不会错但写成简化版能体现出你对不变式的把握。我建议你把这个双指针版本和 3.1 的动规版本对照着看本质上它们算的是同一个东西位置 i 的水量只由“左侧最大”和“右侧最大”中较小的那个决定。双指针的巧妙之处在于它通过控制移动方向保证了被结算那一侧的最大值就是真实最大值另一侧的最大值虽然还未完整探测但已经大到足以成为“限制水位”的那一方。6. 实战踩坑记录从提交失败到对拍通过最后这部分分享几个我实际刷题时踩过的坑以及一套我自己调试这类“累计水量/面积”题目的方法希望你能绕开这些弯路。6.1 最容易翻车的三个细节第一个坑相等高度的处理。在单调栈解法里height[i] height[stack[-1]]用的是严格大于如果改成遇到连续相等高度时会把不该结算的坑底弹出去导致多算水或少算水。比如[2, 2, 2]这种全等高的输入正确输出是 0但用可能会在弹出过程中算出一个负深度或者错位的水量。要理解为什么用严格大于相等高度的柱子之间不会形成凹陷不该触发结算。双指针版本里if height[left] height[right]这个条件左边小于右边时动左边否则动右边——等于的情况归到 else 分支这样能保证左右指针不会因为相等高度而陷入死循环。第二个坑输出类型。虽然题目保证答案在 int 范围内但如果你用width * depth结算时中间结果可能出现较大的值。Python 没有溢出问题但如果是 C 或 Javawidth和depth都是 int相乘可能越界最好直接用 long。很多人代码逻辑没问题测试用例也过了一提交就 WAWrong Answer查了半天发现是乘法溢出这个教训我印象太深了。第三个坑空数组和单元素数组。n 0时直接返回 0。很多模板题解不会特意提这个但 LeetCode 的判题器真的会给空数组。6.2 我是怎么排查逻辑错误的接雨水这类题不像字符串处理肉眼很难直接看出哪一步算错。我的调试套路是三步走小规模手算验证。拿[0,1,0,2,1,0,1,3,2,1,2,1]这类经典用例手动模拟一遍确认预期输出是 6。对拍暴力解。在本地写好trap_brute_force和trap_two_pointers随机生成几百组长度为 0 到 20、高度 0 到 10 的数组逐一对比输出。只要有一组不一致就打印出数组和两个函数的输出定位具体是哪些位置算错了。打印中间状态。如果是单调栈打印每次出栈的下标、计算的 width、depth 和累计 ans如果是双指针打印每次结算时的 left、right、left_max、right_max。中间状态一出来错误点通常立刻现形。这套方法不但适用于接雨水对所有“看起来逻辑简单但就是过不了”的题都有效。我后来刷三维接雨水、柱状图最大矩形都是靠对拍暴力解快速定位问题的。6.3 从二维到三维这道题还能怎么延伸二维接雨水理解了三维接雨水LeetCode 407就顺理成章了。三维版本里水不再是从左右两侧围住而是从上下左右四个方向围住一个格子存水高度取决于“边界最低的那个方向”。解法从双指针升级成“优先队列 BFS”从外圈逐步向内灌水——核心思路仍然是“从最矮的边界向里推进”。很多人在二维和三维之间卡壳就是因为二维的双指针思维惯性太强没有意识到“多个方向”之后必须用优先队列维护“当前最低边界”。把二维彻底吃透三维的入门难度会低很多。最后分享一点个人的刷题心得接雨水这道题我是分三个阶段才真正掌握的。第一个阶段是看题解把代码抄了一遍跑通了就以为会了结果过了两周再写完全想不起来。第二个阶段是理解了核心公式max(0, min(leftMax, rightMax) - height[i])能写出暴力解和动规解面试时候讲起来也算流畅。第三个阶段是有一回面试官追问“双指针的正确性怎么证明”我支支吾吾半天说不清楚回去之后花了一个晚上把暴力、动规、单调栈、双指针四个版本全部手写了一遍又各跑了几百组随机对拍才终于把每一行代码背后的“为什么”钉死在大脑里。所以我的建议是别再背题解了按暴力 - 动态规划 - 单调栈 - 双指针的路径自己把四个版本都写一遍。每次写之前先问你一句这个解法里每个位置的水量是怎么确定的这个信息是提前算好的、还是遍历过程中自然得到的想明白了再动手写完再跑几组对拍验证。这套流程走完接雨水就再也不是一道“背过的题”而是一道“长在脑子里的题”。下次面试官再问起你甚至可以反过来引导他先从暴力讲起再一步步优化这种表现方式比直接默写出最优解要打动人得多。
刷 LeetCode 的朋友应该都有过这种体验一道题看题解秒懂关上页面自己写却卡住。42. 接雨水就是我心中“看懂了但写不出来”的典型代表——我前前后后刷过三遍第一遍背代码第二遍理解公式第三遍才敢说自己真正想明白了。这道题最折磨人的地方在于它不是考你某个冷门 API也不是考复杂的数学推导而是考你有没有建立一套“从物理直觉到算法抽象”的思维链路每个格子到底能存多少水哪些信息必须提前知道哪些信息可以边走边算LeetCode 热题 100 里接雨水稳稳站在“高频中的高频”那一档。不是因为题目本身多难而是因为它像一面镜子暴力法暴露你的建模能力动态规划考察你的空间换时间意识单调栈检验你对“边界结算”的理解双指针则直接反映你能不能看穿最优解背后的不变式。面试官太爱拿它做“思维过程”观察了所以这篇文章我不想再复述一遍标准题解而是按一条完整的探究链路来拆从最笨的暴力开始逐步压缩时间和空间最后落到双指针那个让人拍大腿的解法上。你把这篇文章吃透不光这道题通了靠“左右边界制约”解的一类题也基本通了。1. 为什么几乎所有公司都爱考这道“破柱子”题先聊点题外话。接雨水的题干非常简单给你 n 个非负整数表示宽度为 1 的柱子的高度图计算下雨之后能接多少雨水。输入[0,1,0,2,1,0,1,3,2,1,2,1]输出 6。没了。但就是这个场景能同时撬动好几层能力的考察。第一层是问题建模。很多人一上来就把“能接多少水”等价成“找凹槽面积”然后开始扫描局部极小值——这是个典型的直觉陷阱。柱子之间能存水不是看局部有没有凹陷而是看每个位置左右两边有没有更高的“墙”。建模建错了后面全错。第二层是复杂度意识。暴力解法谁都能写但O(n²)在 n 达到 10^5 或者 2×10^4 的时候直接超时。面试官会追问“能不能优化”这就逼着你从“每个位置现找左右最大”过渡到“提前算好左右最大”。到这一步你其实已经写出了动态规划解法。第三层才是真正的分水岭空间能不能再压缩遍历方向能不能反过来当你能回答“双指针为什么可以边走边结算”你才算真正理解了这题的物理过程而不是背了一个模板。我经常把这道题比作“算法思维的分级体检”暴力法是及格线动态规划是平均水平单调栈说明你见过套路双指针则代表你理解了问题本质。这也是为什么从字节到微软从实习到社招它出现的频率高得离谱。别再问“这题有什么实际应用”了它最大的应用场景就是帮面试官在两轮对话内看清你的算法底子。2. 先搞清楚每一列能存多少水核心公式的推导解题的第一步永远不是写代码而是把“水怎么存”这件事用公式表达出来。这一节我们不谈任何技巧就做一件事把每个柱子上方能接的水量算清楚。2.1 木桶效应在这里的正确打开方式大家都听过“木桶能装多少水取决于最短的那块板”但接雨水这道题里每个格子不是跟全局最矮的柱子比而是跟它左侧最高柱和右侧最高柱分别比。为什么因为水是“局部围住”的某个位置上方能不能存水只取决于它左边有没有柱子挡住、右边有没有柱子挡住以及这两堵墙谁更矮。如果左右两侧任意一侧没有比当前柱子更高的那这个位置存不住水。如果两侧都有更高的柱子那这个位置的水面高度会被较矮的那一侧限制住水位等于min(左侧最高, 右侧最高)。当前柱子的高度本身会占掉一部分空间所以真正能存的水是“限制水位”减去“当前柱高”负数按 0 处理。这就是全题唯一的公式water[i] max(0, min(leftMax[i], rightMax[i]) - height[i])2.2 为什么不能直接跟全局最高柱比假设输入是[3, 0, 0, 2, 0, 4]。全局最高是 4。位置 1 的左侧最高是 3右侧最高是 4水位被 3 限制存水量是 3。位置 3 的左侧最高是 3右侧最高是 4水位也是 3减去自身高度 2存 1。这两个位置都说得通因为它们右侧确实有 4 这个“高墙”。但如果输入变成[5, 0, 0, 2, 0, 3]全局最高是 5。位置 5高度 3的右侧没有比它更高的柱子了它存不了水。可如果简单跟全局最高 5 比min(5, 5) - 3 2那就算错了。所以每个位置都必须看“自己左侧的最大值”和“自己右侧的最大值”而不是全局最大值。或者换个说法右侧最高只考虑当前柱子右边那一段未来不可见。2.3 暴力解法的意义先写对再写快基于这个公式最直接的暴力解法就是遍历每个位置向左扫一遍找最大值向右扫一遍找最大值然后套公式累加。def trap_brute_force(height): n len(height) ans 0 for i in range(n): left_max 0 for j in range(i, -1, -1): left_max max(left_max, height[j]) right_max 0 for j in range(i, n): right_max max(right_max, height[j]) ans max(0, min(left_max, right_max) - height[i]) return ans这个写法没有任何技巧但它有两个不可替代的价值它是后续所有解法的“验证基准”。我调试单调栈和双指针时都是拿这个暴力结果做对拍的——左右区间随机生成几千组数据输出不一致就是代码有 bug。它帮你把“每个位置的水量”这个概念钉死在心里。后续的解法无论多花哨都是在优化left_max和right_max的获取方式而不是在改变这个公式。复杂度就不多说了时间O(n²)空间O(1)。leetcode 上一跑n 稍微大一点就超时但这种“先能算对再追求效率”的思路反而是我建议所有刷题新手养成的习惯。3. 用预处理换时间动态规划解法里藏着的通用思想暴力法慢在哪儿每个位置都要重新向左、向右扫描一遍而且大量扫描是重复的。位置 i 和位置 i1 的左侧最大值之间明明只差一个height[i1]的比较暴力法却把前面所有柱子重新扫了一遍。这种“重复计算”就是优化的信号。3.1 前缀最大与后缀最大数组的构造动态规划解法做了一件非常朴素的事把每个位置的左右最大值提前算好存进数组。左边最大值数组leftMax[i]表示height[0..i]的最大值右边最大值数组rightMax[i]表示height[i..n-1]的最大值。def trap_dp(height): n len(height) if n 0: return 0 left_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 [0] * n 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(n): ans max(0, min(left_max[i], right_max[i]) - height[i]) return ans两个数组的递推关系就是标准的“前缀最值”和“后缀最值”left_max[i]只依赖left_max[i-1]和height[i]right_max[i]只依赖right_max[i1]和height[i]。这就是动态规划里的“无后效性”——当前状态只由前置状态决定不需要回退重算。时间降到了O(n)代价是O(n)的额外空间。很多第一次接触这个解法的朋友会困惑“这不是空间换时间吗面试官会不会觉得不够优”如果面试官不追问这个答案已经合格了。但如果你能主动补一句“空间上还能优化到 O(1)”印象分会明显不一样。这正是接雨水这道题精妙的地方它逼着你把“能用数组存”进化到“连数组都省掉”。3.2 这类“预处理数组”思路在热题里的普适性接雨水不是唯一需要前缀/后缀信息的题。LeetCode 热题 100 里有好几道都是同一个套路我整理一下你对照着看会非常有感觉题目预处理思路和接雨水的关联238. 除自身以外数组的乘积前缀积 后缀积同样是先预处理“左右两侧信息”再按位置合并739. 每日温度从右往左遍历配合栈或数组记录后缀信息的递推和 right_max 的构造思路一致84. 柱状图中最大的矩形单调栈找左右边界和接雨水的单调栈解法互为镜像一个是围水一个是扩矩形说白了很多题目表面上千变万化底层都是在问同一件事每个位置能不能用 O(1) 时间拿到“左侧某种极值/累计值”和“右侧某种极值/累计值”。脑子里装着这个框架下次遇到“每个元素要跟左右比较”的题第一反应就不再是“怎么遍历”而是“能不能预处理”。当然空间 O(n) 也留下了优化空间——接雨水的最优解就是把这两个数组变成两个变量。4. 单调栈换一种视角从“按列算”到“按层结算”如果说动规解法的思维是“站在每一列上方看它能存多少水”那单调栈解法的思维就是“站在水面上看每一层水是被哪两根柱子围出来的”。这是两种完全不同的建模方式也是很多人第一次接触时最懵的地方。4.1 单调栈到底在维护什么先说结论我们维护一个从栈底到栈顶高度单调递减的下标栈。遍历每个柱子时只要当前柱子高度小于等于栈顶柱子高度就把它压进栈里——相当于“当前还没有找到比它更高的右墙”。一旦当前柱子的高度大于栈顶柱子的高度说明栈顶这根柱子的“右墙”出现了可以结算它作为坑底时能存的水。这里的关键是出栈的栈顶元素是“坑底”新的栈顶元素是“左墙”当前遍历到的元素是“右墙”。水的深度等于min(左墙高, 右墙高) - 坑底高水的宽度等于右墙下标 - 左墙下标 - 1。注意这里的宽度是“坑底位置到左墙之间”的水平距离这就是为什么这种视角叫“按层结算”。用代码说话def trap_stack(height): stack [] ans 0 n len(height) for i in range(n): while stack and height[i] height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] width i - left - 1 depth min(height[left], height[i]) - height[bottom] ans width * depth stack.append(i) return ansbreak那个分支很关键如果弹出坑底后栈空了说明左边没有更高的墙这次无法形成水坑直接跳出循环把当前柱子压入栈中。这不是边界情况而是常见的空栈场景——比如数组一开始是递减的前两根柱子之间根本存不了水。4.2 手动推演一个例子拿题目自带的[0,1,0,2,1,0,1,3,2,1,2,1]来走前几步i0栈空压入 0。i1height[1]1 height[0]0弹出 0 作为坑底栈空无左墙不结算。压入 1。i2height[2]0 height[1]1压入 2。此时栈底到栈顶为 [1, 2]高度 [1, 0]。i3height[3]2 height[2]0弹出 2 作为坑底左墙是栈顶 1右墙是当前 3。width3-1-11depthmin(1,2)-01ans 加 1。栈变成 [1]height[3]2 仍然大于 height[1]1再弹出 1栈空无左墙不结算。压入 3。这一步恰好就是教科书里的“第一个水坑”下标 2 的位置被高度 1 的柱子下标1和高度 2 的柱子下标3围住存了 1 单位水。继续往下走你会发现单调栈结算的不是一个完整的大凹槽而是“一层一层”地结算。下标 4 到 6 那个小坑以及后面更大的坑都是在遍历过程中逐步按层累加的。这也是它和动规解法最大的差异动规站在列的视角水是竖向一块一块累计的单调栈站在行的视角水是横向一层一层累计的。4.3 什么时候该想到单调栈很多读者问过我“我知道单调栈这个数据结构但怎么判断一道题该用它”我的经验就三条题目里出现“找左边/右边第一个比当前元素大或小的元素”这类描述这基本是单调栈的正面信号。计算某个区间内的“围成面积”“水量”“最大矩形”时如果这个量的定义和“两侧边界的高度/位置”强相关单调栈往往能直接把边界维护在栈里。你已经写出了一个 n² 或需要反复寻边的解法且遍历方向与边界判断相关时可以主动往单调栈上靠一靠。接雨水恰好在第 2 条和第 3 条的交汇处。84. 柱状图中最大的矩形也是这两个条件都满足的一道题你可以把两题放一起对比着做。顺便提醒一句接雨水的单调栈维护的是“递减栈”84 题维护的是“递增栈”两者恰好相反千万别背反。5. 双指针从 O(n) 空间到 O(1) 空间的临门一脚到了这一节我们要解决最后一个问题两个预处理数组能不能省略答案是能而且省略的方式一不小心就会绕晕人。先说结论双指针解法不是动规的简单压缩它背后站着一个非常强的“位置结算不变式”。5.1 为什么左右指针敢边走边算双指针解法的代码极其简洁def trap_two_pointers(height): left, right 0, len(height) - 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 height[left] height[right]: ans left_max - height[left] left 1 else: ans right_max - height[right] right - 1 return ans很多第一次看到这个写法的人都会问处理height[left] height[right]的左边分支时right_max明明只是“右边已经扫描过的最大值”右边还没走完怎么能确定左边位置的水量答案是这个位置的接水量根本不需要知道右边完整的信息。我们用一个生活化的场景来解释。假设你站在一排柱子中间左边最高的柱子已经确定是 5 米右边你目前看到最高的柱子是 7 米而且你正站在一根 3 米的柱子旁边。这时问你脚下这根 3 米柱子能存多少水你会说水位最高到 5 米存 2 米。为什么右边后面可能还有 100 米的柱子也不影响因为水面高度取的是左右最大值的较小者左边封顶 5 米右边就算出现更高的min(左边最大, 右边最大)也不会超过 5 米。反过来如果左边最大值是 5 米右边目前只看到 3 米那右边这根柱子的水量也已经被右边的 3 米封顶了吗不是因为左边已经确定有 5 米了右边一旦后续出现更高的柱子水位会上涨。所以这时不能结算右边柱子反而应该继续移动右指针去“探测”右边更高的可能性。当右边 max 小于等于左边 max 时右边的水量才稳定。双指针的循环就是这样每次比较height[left]和height[right]的大小小的那一侧它的接水量已经由当前维护的left_max和right_max的较小者决定了可以直接结算并移动指针大的一侧暂时不结算因为它可能还有“更好的右墙”没探到。这个思路本质上就是“哪边更矮就先处理哪边因为矮的那边已经不可能被更高的墙改变了”。5.2 边界条件与常见误区双指针代码虽然短但有几个地方特别容易出岔子初始化时left_max和right_max必须先更新再算水。我第一次写的时候把left_max max(left_max, height[left])放到了结算之后结果第一个位置直接出现负数。先更新是为了保证当前柱子的高度已经纳入“墙”的候选否则你结算的是“还没看过当前位置”时的信息。循环条件是left right不是left right。当左右指针相遇时中间只剩一堵墙不可能再接水所以不用处理。结算时用的是left_max - height[left]而不是min(left_max, right_max) - height[left]。因为在这个分支里left_max right_max一定成立否则会走 else所以min就是left_max。同理else 分支里用right_max。这里直接套公式也不会错但写成简化版能体现出你对不变式的把握。我建议你把这个双指针版本和 3.1 的动规版本对照着看本质上它们算的是同一个东西位置 i 的水量只由“左侧最大”和“右侧最大”中较小的那个决定。双指针的巧妙之处在于它通过控制移动方向保证了被结算那一侧的最大值就是真实最大值另一侧的最大值虽然还未完整探测但已经大到足以成为“限制水位”的那一方。6. 实战踩坑记录从提交失败到对拍通过最后这部分分享几个我实际刷题时踩过的坑以及一套我自己调试这类“累计水量/面积”题目的方法希望你能绕开这些弯路。6.1 最容易翻车的三个细节第一个坑相等高度的处理。在单调栈解法里height[i] height[stack[-1]]用的是严格大于如果改成遇到连续相等高度时会把不该结算的坑底弹出去导致多算水或少算水。比如[2, 2, 2]这种全等高的输入正确输出是 0但用可能会在弹出过程中算出一个负深度或者错位的水量。要理解为什么用严格大于相等高度的柱子之间不会形成凹陷不该触发结算。双指针版本里if height[left] height[right]这个条件左边小于右边时动左边否则动右边——等于的情况归到 else 分支这样能保证左右指针不会因为相等高度而陷入死循环。第二个坑输出类型。虽然题目保证答案在 int 范围内但如果你用width * depth结算时中间结果可能出现较大的值。Python 没有溢出问题但如果是 C 或 Javawidth和depth都是 int相乘可能越界最好直接用 long。很多人代码逻辑没问题测试用例也过了一提交就 WAWrong Answer查了半天发现是乘法溢出这个教训我印象太深了。第三个坑空数组和单元素数组。n 0时直接返回 0。很多模板题解不会特意提这个但 LeetCode 的判题器真的会给空数组。6.2 我是怎么排查逻辑错误的接雨水这类题不像字符串处理肉眼很难直接看出哪一步算错。我的调试套路是三步走小规模手算验证。拿[0,1,0,2,1,0,1,3,2,1,2,1]这类经典用例手动模拟一遍确认预期输出是 6。对拍暴力解。在本地写好trap_brute_force和trap_two_pointers随机生成几百组长度为 0 到 20、高度 0 到 10 的数组逐一对比输出。只要有一组不一致就打印出数组和两个函数的输出定位具体是哪些位置算错了。打印中间状态。如果是单调栈打印每次出栈的下标、计算的 width、depth 和累计 ans如果是双指针打印每次结算时的 left、right、left_max、right_max。中间状态一出来错误点通常立刻现形。这套方法不但适用于接雨水对所有“看起来逻辑简单但就是过不了”的题都有效。我后来刷三维接雨水、柱状图最大矩形都是靠对拍暴力解快速定位问题的。6.3 从二维到三维这道题还能怎么延伸二维接雨水理解了三维接雨水LeetCode 407就顺理成章了。三维版本里水不再是从左右两侧围住而是从上下左右四个方向围住一个格子存水高度取决于“边界最低的那个方向”。解法从双指针升级成“优先队列 BFS”从外圈逐步向内灌水——核心思路仍然是“从最矮的边界向里推进”。很多人在二维和三维之间卡壳就是因为二维的双指针思维惯性太强没有意识到“多个方向”之后必须用优先队列维护“当前最低边界”。把二维彻底吃透三维的入门难度会低很多。最后分享一点个人的刷题心得接雨水这道题我是分三个阶段才真正掌握的。第一个阶段是看题解把代码抄了一遍跑通了就以为会了结果过了两周再写完全想不起来。第二个阶段是理解了核心公式max(0, min(leftMax, rightMax) - height[i])能写出暴力解和动规解面试时候讲起来也算流畅。第三个阶段是有一回面试官追问“双指针的正确性怎么证明”我支支吾吾半天说不清楚回去之后花了一个晚上把暴力、动规、单调栈、双指针四个版本全部手写了一遍又各跑了几百组随机对拍才终于把每一行代码背后的“为什么”钉死在大脑里。所以我的建议是别再背题解了按暴力 - 动态规划 - 单调栈 - 双指针的路径自己把四个版本都写一遍。每次写之前先问你一句这个解法里每个位置的水量是怎么确定的这个信息是提前算好的、还是遍历过程中自然得到的想明白了再动手写完再跑几组对拍验证。这套流程走完接雨水就再也不是一道“背过的题”而是一道“长在脑子里的题”。下次面试官再问起你甚至可以反过来引导他先从暴力讲起再一步步优化这种表现方式比直接默写出最优解要打动人得多。
