这道题我在力扣上刷过好几遍每次隔一段时间再回头看都会有新的理解。作为热题100里的常客接雨水是那种典型的“一看答案就会合上书就废”的题目——二分、双指针、动态规划、单调栈四种主流解法背后其实是四种不同的思维模型。把这道题真正吃透绝对值回票价。先说清楚一个基本认知接雨水这道题叫“Hard”但很多人做完之后的体感是“也就中等难度”。原因在于它的思路本身不复杂真正折磨人的是边界条件、等号处理和空间复杂度的优化细节。很多人第一眼看到题目觉得简单一写代码就翻车这种“眼高手低”的体验本身就说明这道题的水很深。这篇文章我打算把四种解法全部拆开揉碎讲一遍从最直观的暴力思路出发一步步优化到双指针和单调栈顺便把我在刷题中踩过的坑、总结出来的避错经验都放进来。无论你是刚开始刷力扣的新手还是在冲刺面试的中段选手这篇文章应该能给你一些不一样的启发。1. 先读懂题目接雨水到底在算什么1.1 一个生活化的理解方式题目给你一个数组每个数字代表一根柱子的高度。下雨之后低洼的地方会积水问总降水量是多少。我第一次看这道题的时候脑子里直接把它想象成山峦的侧影。左边一座山右边一座山中间有个山谷雨水就会囤在谷里。问题是现实中的山谷是连续的斜坡而题目的柱子是离散的、一格一格的每根柱子宽1高不同。雨水只会积在柱子的间隙之间。一句话总结每一格宽度为1的柱位能接多少水完全取决于它左右两边最高柱子的较矮那一根再减去自身柱子的高度。如果自身比两边都高那么这一格就是“山脊”不积水如果自身处于低洼那么水就会囤到两边较矮的墙顶那么高。这个理解非常重要它是后面一切解法的起点。简单来说接雨水问题可以拆解成“按列计算”每一列能存多少水然后用宽度1去乘最后把每一列的积水量加起来。1.2 为什么不能用二维的思路硬套有些同学会把接雨水和“盛最多水的容器”搞混这两道题确实很容易弄混。容器那题是找两根柱子围成的最大面积本质是找一对柱子的组合问题而接雨水是计算所有低洼区域的积水总和本质是每个位置独立的积水计算问题。如果你用容器那题的思维去接雨水很容易走进死胡同——你会去试图找到某个“最优区间”但实际上接雨水不是找一个区间而是对全数组做统计。每根柱子都在扮演两个角色它既可能是挡住水的墙壁也可能是被水淹没的低洼点。这种双重身份也是很多解法看起来“绕”的根本原因。想明白这一层你就能理解为什么暴力解是先把每个位置的左右最高值求出来然后逐列累加。虽然时间复杂度高但它把“按列计算”这个本质暴露得最彻底。后面所有的优化其实都是在“如何更快地知道某个位置的左右最高值”这件事上做文章。2. 暴力思路与动态规划先把框架搭对2.1 从读题到可运行的暴力代码很多刷题老手会跳过暴力解直接上最优解。但我的建议是接雨水这种题目恰恰适合从暴力开始做因为这个过程能帮你把“按列计算”的逻辑彻底刻在脑子里。暴力解法非常简单对于数组中的每一根柱子向左边扫描找到左边的最大高度向右边扫描找到右边的最大高度取两者的较小值再减去当前柱子的高度就是这一格的积水量。如果这个值大于0就累加到答案里。def trap_brutal(height): n len(height) ans 0 for i in range(n): left_max max(height[:i1]) right_max max(height[i:]) ans min(left_max, right_max) - height[i] return ans这个代码完全没有技巧就是照抄思路。每个位置都要扫一遍左右两边总复杂度是O(n²)遇到长数组会超时。但它的正确性是毫无疑问的作为第一版实现它可以帮你验证自己对题意的理解是否准确。在本地跑一下样例height [0,1,0,2,1,0,1,3,2,1,2,1]得到6和题目一致。这个样例非常经典我强烈建议你把它手动推一遍哪怕只是拿笔在纸上画柱状图也比直接看十遍代码有效。2.2 动态规划优化预计算前后缀最大值暴力解慢在哪里慢在每个位置都要重复扫描左右两侧。但其实每个位置的左侧最大值和右侧最大值是可以通过一次遍历预计算出来的。这就是动态规划的思想用两个数组分别记录每个位置左侧的峰值和右侧的峰值。左边扫描一遍left_max[i] max(left_max[i-1], height[i])表示从0到i这些柱子的最高高度。右边扫描一遍right_max[i] max(right_max[i1], height[i])表示从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[i1], height[i]) ans 0 for i in range(n): ans min(left_max[i], right_max[i]) - height[i] return ans这个解法的时间复杂度降到O(n)空间复杂度是O(n)。它比暴力解优雅得多也是面试时一个很好的过渡解释——你向面试官展示了你看到了暴力解的问题并且提出了“空间换时间”的方案。不过动态规划版本有一个隐蔽的逻辑点min(left_max[i], right_max[i]) - height[i]可能出现负数吗不会因为left_max[i]和right_max[i]至少包含height[i]本身所以它们的较小值一定不矮于当前柱子。这就是为什么这个公式可以直接累加不需要判断正负。3. 双指针解法面试官最想看到的答案3.1 双指针为什么能省空间动态规划版本的时间已经很理想但空间复杂度还能进一步优化。这就是双指针解法的价值所在——它在保持O(n)时间复杂度的同时把空间复杂度压到O(1)。面试的时候能在白板上写出这个版本基本就是这道题目的满分答卷。双指针的核心洞察是我们并不需要确切知道每个位置的左右最大值只需要知道“左右最大值中较小的那一个”。思考过程是这样的维护两个指针一个从左边走一个从右边走同时维护左侧当前看到的最高值和右侧当前看到的最高值。当左边的最高值比较小时左指针指向的位置能接多少水已经被左侧限制了——即使右侧某处有一根无限高的柱子水也不可能越过左边这根较矮的“墙”。反过来同理。这就是双指针移动的判断依据哪边的最高值更矮就移动哪边的指针并结算对应位置的积水量。3.2 代码实现与边界条件处理来看代码def trap_two_pointer(height): if not height: return 0 left, right 0, len(height) - 1 left_max, right_max height[left], height[right] ans 0 while left right: if left_max right_max: left 1 left_max max(left_max, height[left]) ans left_max - height[left] else: right - 1 right_max max(right_max, height[right]) ans right_max - height[right] return ans这段代码看起来很紧凑但每一行都值得仔细推敲。先说核心的移动规则left_max right_max时移动左指针否则移动右指针。等于号归到哪边都行对结果没有影响。原因在于当两边最高值相等时无论结算哪一边当前能接的水量都是“墙高减去自身高度”结果一样。再仔细看结算逻辑左指针移动前先让left指针指向新位置然后更新left_max最后累加left_max - height[left]。这里有一个非常容易踩的坑是如果先结算再移动指针就会漏算或者多算。因为left_max是“从0位置到当前左指针位置”的扫描最大值它必须在指针移动后立即更新才能保证计算的是当前柱子的左侧峰值。关于等号的处理我再说细一点如果left_max right_max走了else分支移动右指针。此时右指针向左移动更新right_max然后累加。这个逻辑和左移完全对称。有些同学会问如果left指针指向的柱子本身比left_max高怎么办不会的因为left_max是已经扫描过的区间最大值而当前left位置一定是之前扫描过的位置所以left_max - height[left]非负。双指针解法的精妙之处在于它把动态规划的两个数组压缩成了两个变量因为我们只在指针移动时用到“已遇到的最大值”而这些最大值恰好只与当前扫描的方向有关。如果你第一次看懂这个解法恭喜你你对“空间优化”这件事的理解会上一个台阶。4. 单调栈解法从“槽”的视角重新理解4.1 单调栈在接雨水里到底存什么如果说双指针是“按列计算”的极致优化那单调栈就是完全不同的视角按行计算。这个视角比较抽象也是很多同学觉得接雨水难的地方。单调栈的思路是维护一个栈栈底到栈顶按照柱子高度递减。也就是说栈顶是最矮的柱子。当遍历到一个新柱子时如果它比栈顶柱子高那么栈顶和下个栈顶之间的区域就形成了一个可以接水的“槽”。弹出栈顶计算以它为底、以左右两侧较高柱子为边的积水量。关键区别在于单调栈不是一列一列地算而是找到一个个“凹槽”一次算一格。计算体积时用的是“宽度 × 高度”宽度是当前索引与左边界索引的间隔高度是两侧较矮墙的高度减去槽底的高度。这就是我前边说的“按行计算”的直觉来源——每一层水对应一个宽阔的区域。单调栈里存的是下标不是值。这一个细节很多人会忽略。为什么要存下标因为计算宽度时必须用到索引差。如果只存值宽度就算不出来代码也就废了。4.2 栈解法代码与常见坑def trap_stack(height): stack [] ans 0 for i, h in enumerate(height): while stack and h height[stack[-1]]: top stack.pop() if not stack: break left stack[-1] width i - left - 1 height_diff min(height[left], h) - height[top] ans width * height_diff stack.append(i) return ans这段代码我第一次写的时候break那一行完全没有想到。后来才发现如果弹出的栈顶元素左侧没有其他柱子了说明这个位置虽然有高度差但左边没有“墙”挡住水会流走所以不能积水必须直接break。还有一个隐藏的坑遇到相同高度的柱子时不要急着弹栈。因为两根等高的柱子之间无法积水水会从中间流走。等于号的处理方式是不弹出直接让新柱子入栈。这样栈里会存在高度相同的下标但后面遇到更高的柱子时最后一次弹出会正确计算水量。这个细节我对比过数值弹与不弹结果一样但弹了会平白增加计算量没必要。单调栈的时间复杂度是O(n)空间复杂度也是O(n)最坏情况是数组升序时栈里存了所有柱子。以我个人的体会单调栈的理解成本最高但写出来的代码却非常简短优雅。面试时如果能在双指针之后顺带提一句单调栈解法会是一个很好的加分展示。它证明你对这道题的理解不只是一个套路而是多个维度。5. 解题模板对比与刷题要点5.1 四种解法复杂度分析把四种解法放到一张表里对比看起来就更清晰了解法时间复杂度空间复杂度思维视角面试推荐度暴力扫描O(n²)O(1)按列计算不推荐提交但适合验证思路动态规划O(n)O(n)按列计算预计算适合作为过渡思路双指针O(n)O(1)按列计算空间压缩最推荐兼顾清晰与高效单调栈O(n)O(n)按行计算凹槽加分项展示多维度理解从实际面试的角度看动态规划和双指针最值得熟练掌握。暴力解适合在纸上推演的时候帮助你理清思路。单调栈更像是“文化课选修”会了是亮点不会也不致命但如果你准备的是大厂面试建议还是掌握。因为单调栈的应用范围很广不只是接雨水很多区间类问题都会用到。5.2 易错点汇总这些都是我踩过的坑第一个坑是忘记处理空数组。我一直强调力扣刷题第一行先判断边界if not height: return 0。尤其是用Python刷题时输入为[]的情况很容易被忽略而一旦忽略就会报索引错误。第二个坑是双指针的相等判断。当left_max right_max时走else分支移动右指针不会影响结果但有些同学会在这里纠结很久。我的建议是别纠结选一种写法跑一遍样例验证结果正确即可。力扣的判定只看最终值是否正确不看移动路径。第三个坑是单调栈的break条件。前面已经提到了栈弹出后为空说明左边没有墙无法积水必须跳出内层循环。少了这一句数组[3, 2, 1]这种纯递减场景就会算错。第四个坑是把下标和值搞混。单调栈存下标双指针存值。这个看似简单的区别在实际编码时非常容易搞乱。写单调栈时取高度一定要用height[stack[-1]]而不是stack[-1]。类似的错误我犯过好几次每次都得靠单元测试帮我揪出来。易错点错误示范正确做法空数组未处理直接访问height[0]先判断长度是否为0双指针等号不确定纠结不移动选一边移动即可结果不变单调栈break缺失栈空仍继续计算栈空说明无左墙break单调栈存值而非下标存value无法算宽度存下标宽度用索引差6. 从接雨水到一类题的解题框架6.1 同类题型的识别标志接雨水不是一道孤立的题它属于一个很典型的题型家族。这类题目的共同特点是数组本身代表某种高度或宽度需要你计算在这些约束条件下形成的“区域面积”或“可容纳量”。再看一遍题目特征你会发现它们有明显的识别标志——数组中存在“峰值”和“低谷”的相对关系计算结果与“较矮的一侧”有关。最典型的同类题就是力扣11题“盛最多水的容器”。那题简单一些只需要双指针从两端夹逼即可核心是移动较矮的一侧。力扣84题“柱状图中最大的矩形”则是单调栈的经典应用和接雨水的单调栈解法互为镜像——一个求存水一个求矩形面积栈的维护逻辑刚好相反。把这两道题对着刷你会对单调栈有脱胎换骨的理解。二维版本的接雨水力扣407题“接雨水 II”则是把一维的双指针/优先队列思想扩展到二维算是一个不错的进阶。我的建议是先刷完接雨水和柱状图最大矩形再去挑战二维版本不然挫败感会很强。6.2 刷题顺序与刻意练习建议如果你正在刷力扣热题100我建议你按这样的顺序来安排这几道题先做11题盛最多水的容器它是最简单的双指针入门题三分钟就能搞定再做42题接雨水用双指针解决它巩固移动较矮一侧的思维模型然后做84题柱状图中最大的矩形从中对比单调栈和接雨水在使用时的不同细节。这个顺序下来你会发现在做接雨水时积累的“较矮决定论”直觉在做容器题时只需要一次练习就能建立而84题会反过来帮你检验是否真正理解了单调栈中“弹出”的时机。还有一个实操建议刷完一道题后隔三天再重新默写一遍代码。尤其是接雨水这种思路多、细节多的题你会发现第一次写的时候觉得完全理解了隔几天再写还是会卡在某个边界条件上。这种“回生”是完全正常的恰恰说明你还没有把解法真正内化。多来几次“遗忘-重新理解”的过程这段代码才会彻底长在你脑子里。我在实际刷题中发现把双指针版本和单调栈版本都写到熟练之后再去写很多其他难题都会顺手得多。因为它们本质上训练的是同一件事如何在遍历过程中用最少的额外信息维护出解决问题所需的关键状态。这个能力远比记住某一道题的固定解法重要得多。
接雨水问题全解析：四大解法与双指针、单调栈优化思路
这道题我在力扣上刷过好几遍每次隔一段时间再回头看都会有新的理解。作为热题100里的常客接雨水是那种典型的“一看答案就会合上书就废”的题目——二分、双指针、动态规划、单调栈四种主流解法背后其实是四种不同的思维模型。把这道题真正吃透绝对值回票价。先说清楚一个基本认知接雨水这道题叫“Hard”但很多人做完之后的体感是“也就中等难度”。原因在于它的思路本身不复杂真正折磨人的是边界条件、等号处理和空间复杂度的优化细节。很多人第一眼看到题目觉得简单一写代码就翻车这种“眼高手低”的体验本身就说明这道题的水很深。这篇文章我打算把四种解法全部拆开揉碎讲一遍从最直观的暴力思路出发一步步优化到双指针和单调栈顺便把我在刷题中踩过的坑、总结出来的避错经验都放进来。无论你是刚开始刷力扣的新手还是在冲刺面试的中段选手这篇文章应该能给你一些不一样的启发。1. 先读懂题目接雨水到底在算什么1.1 一个生活化的理解方式题目给你一个数组每个数字代表一根柱子的高度。下雨之后低洼的地方会积水问总降水量是多少。我第一次看这道题的时候脑子里直接把它想象成山峦的侧影。左边一座山右边一座山中间有个山谷雨水就会囤在谷里。问题是现实中的山谷是连续的斜坡而题目的柱子是离散的、一格一格的每根柱子宽1高不同。雨水只会积在柱子的间隙之间。一句话总结每一格宽度为1的柱位能接多少水完全取决于它左右两边最高柱子的较矮那一根再减去自身柱子的高度。如果自身比两边都高那么这一格就是“山脊”不积水如果自身处于低洼那么水就会囤到两边较矮的墙顶那么高。这个理解非常重要它是后面一切解法的起点。简单来说接雨水问题可以拆解成“按列计算”每一列能存多少水然后用宽度1去乘最后把每一列的积水量加起来。1.2 为什么不能用二维的思路硬套有些同学会把接雨水和“盛最多水的容器”搞混这两道题确实很容易弄混。容器那题是找两根柱子围成的最大面积本质是找一对柱子的组合问题而接雨水是计算所有低洼区域的积水总和本质是每个位置独立的积水计算问题。如果你用容器那题的思维去接雨水很容易走进死胡同——你会去试图找到某个“最优区间”但实际上接雨水不是找一个区间而是对全数组做统计。每根柱子都在扮演两个角色它既可能是挡住水的墙壁也可能是被水淹没的低洼点。这种双重身份也是很多解法看起来“绕”的根本原因。想明白这一层你就能理解为什么暴力解是先把每个位置的左右最高值求出来然后逐列累加。虽然时间复杂度高但它把“按列计算”这个本质暴露得最彻底。后面所有的优化其实都是在“如何更快地知道某个位置的左右最高值”这件事上做文章。2. 暴力思路与动态规划先把框架搭对2.1 从读题到可运行的暴力代码很多刷题老手会跳过暴力解直接上最优解。但我的建议是接雨水这种题目恰恰适合从暴力开始做因为这个过程能帮你把“按列计算”的逻辑彻底刻在脑子里。暴力解法非常简单对于数组中的每一根柱子向左边扫描找到左边的最大高度向右边扫描找到右边的最大高度取两者的较小值再减去当前柱子的高度就是这一格的积水量。如果这个值大于0就累加到答案里。def trap_brutal(height): n len(height) ans 0 for i in range(n): left_max max(height[:i1]) right_max max(height[i:]) ans min(left_max, right_max) - height[i] return ans这个代码完全没有技巧就是照抄思路。每个位置都要扫一遍左右两边总复杂度是O(n²)遇到长数组会超时。但它的正确性是毫无疑问的作为第一版实现它可以帮你验证自己对题意的理解是否准确。在本地跑一下样例height [0,1,0,2,1,0,1,3,2,1,2,1]得到6和题目一致。这个样例非常经典我强烈建议你把它手动推一遍哪怕只是拿笔在纸上画柱状图也比直接看十遍代码有效。2.2 动态规划优化预计算前后缀最大值暴力解慢在哪里慢在每个位置都要重复扫描左右两侧。但其实每个位置的左侧最大值和右侧最大值是可以通过一次遍历预计算出来的。这就是动态规划的思想用两个数组分别记录每个位置左侧的峰值和右侧的峰值。左边扫描一遍left_max[i] max(left_max[i-1], height[i])表示从0到i这些柱子的最高高度。右边扫描一遍right_max[i] max(right_max[i1], height[i])表示从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[i1], height[i]) ans 0 for i in range(n): ans min(left_max[i], right_max[i]) - height[i] return ans这个解法的时间复杂度降到O(n)空间复杂度是O(n)。它比暴力解优雅得多也是面试时一个很好的过渡解释——你向面试官展示了你看到了暴力解的问题并且提出了“空间换时间”的方案。不过动态规划版本有一个隐蔽的逻辑点min(left_max[i], right_max[i]) - height[i]可能出现负数吗不会因为left_max[i]和right_max[i]至少包含height[i]本身所以它们的较小值一定不矮于当前柱子。这就是为什么这个公式可以直接累加不需要判断正负。3. 双指针解法面试官最想看到的答案3.1 双指针为什么能省空间动态规划版本的时间已经很理想但空间复杂度还能进一步优化。这就是双指针解法的价值所在——它在保持O(n)时间复杂度的同时把空间复杂度压到O(1)。面试的时候能在白板上写出这个版本基本就是这道题目的满分答卷。双指针的核心洞察是我们并不需要确切知道每个位置的左右最大值只需要知道“左右最大值中较小的那一个”。思考过程是这样的维护两个指针一个从左边走一个从右边走同时维护左侧当前看到的最高值和右侧当前看到的最高值。当左边的最高值比较小时左指针指向的位置能接多少水已经被左侧限制了——即使右侧某处有一根无限高的柱子水也不可能越过左边这根较矮的“墙”。反过来同理。这就是双指针移动的判断依据哪边的最高值更矮就移动哪边的指针并结算对应位置的积水量。3.2 代码实现与边界条件处理来看代码def trap_two_pointer(height): if not height: return 0 left, right 0, len(height) - 1 left_max, right_max height[left], height[right] ans 0 while left right: if left_max right_max: left 1 left_max max(left_max, height[left]) ans left_max - height[left] else: right - 1 right_max max(right_max, height[right]) ans right_max - height[right] return ans这段代码看起来很紧凑但每一行都值得仔细推敲。先说核心的移动规则left_max right_max时移动左指针否则移动右指针。等于号归到哪边都行对结果没有影响。原因在于当两边最高值相等时无论结算哪一边当前能接的水量都是“墙高减去自身高度”结果一样。再仔细看结算逻辑左指针移动前先让left指针指向新位置然后更新left_max最后累加left_max - height[left]。这里有一个非常容易踩的坑是如果先结算再移动指针就会漏算或者多算。因为left_max是“从0位置到当前左指针位置”的扫描最大值它必须在指针移动后立即更新才能保证计算的是当前柱子的左侧峰值。关于等号的处理我再说细一点如果left_max right_max走了else分支移动右指针。此时右指针向左移动更新right_max然后累加。这个逻辑和左移完全对称。有些同学会问如果left指针指向的柱子本身比left_max高怎么办不会的因为left_max是已经扫描过的区间最大值而当前left位置一定是之前扫描过的位置所以left_max - height[left]非负。双指针解法的精妙之处在于它把动态规划的两个数组压缩成了两个变量因为我们只在指针移动时用到“已遇到的最大值”而这些最大值恰好只与当前扫描的方向有关。如果你第一次看懂这个解法恭喜你你对“空间优化”这件事的理解会上一个台阶。4. 单调栈解法从“槽”的视角重新理解4.1 单调栈在接雨水里到底存什么如果说双指针是“按列计算”的极致优化那单调栈就是完全不同的视角按行计算。这个视角比较抽象也是很多同学觉得接雨水难的地方。单调栈的思路是维护一个栈栈底到栈顶按照柱子高度递减。也就是说栈顶是最矮的柱子。当遍历到一个新柱子时如果它比栈顶柱子高那么栈顶和下个栈顶之间的区域就形成了一个可以接水的“槽”。弹出栈顶计算以它为底、以左右两侧较高柱子为边的积水量。关键区别在于单调栈不是一列一列地算而是找到一个个“凹槽”一次算一格。计算体积时用的是“宽度 × 高度”宽度是当前索引与左边界索引的间隔高度是两侧较矮墙的高度减去槽底的高度。这就是我前边说的“按行计算”的直觉来源——每一层水对应一个宽阔的区域。单调栈里存的是下标不是值。这一个细节很多人会忽略。为什么要存下标因为计算宽度时必须用到索引差。如果只存值宽度就算不出来代码也就废了。4.2 栈解法代码与常见坑def trap_stack(height): stack [] ans 0 for i, h in enumerate(height): while stack and h height[stack[-1]]: top stack.pop() if not stack: break left stack[-1] width i - left - 1 height_diff min(height[left], h) - height[top] ans width * height_diff stack.append(i) return ans这段代码我第一次写的时候break那一行完全没有想到。后来才发现如果弹出的栈顶元素左侧没有其他柱子了说明这个位置虽然有高度差但左边没有“墙”挡住水会流走所以不能积水必须直接break。还有一个隐藏的坑遇到相同高度的柱子时不要急着弹栈。因为两根等高的柱子之间无法积水水会从中间流走。等于号的处理方式是不弹出直接让新柱子入栈。这样栈里会存在高度相同的下标但后面遇到更高的柱子时最后一次弹出会正确计算水量。这个细节我对比过数值弹与不弹结果一样但弹了会平白增加计算量没必要。单调栈的时间复杂度是O(n)空间复杂度也是O(n)最坏情况是数组升序时栈里存了所有柱子。以我个人的体会单调栈的理解成本最高但写出来的代码却非常简短优雅。面试时如果能在双指针之后顺带提一句单调栈解法会是一个很好的加分展示。它证明你对这道题的理解不只是一个套路而是多个维度。5. 解题模板对比与刷题要点5.1 四种解法复杂度分析把四种解法放到一张表里对比看起来就更清晰了解法时间复杂度空间复杂度思维视角面试推荐度暴力扫描O(n²)O(1)按列计算不推荐提交但适合验证思路动态规划O(n)O(n)按列计算预计算适合作为过渡思路双指针O(n)O(1)按列计算空间压缩最推荐兼顾清晰与高效单调栈O(n)O(n)按行计算凹槽加分项展示多维度理解从实际面试的角度看动态规划和双指针最值得熟练掌握。暴力解适合在纸上推演的时候帮助你理清思路。单调栈更像是“文化课选修”会了是亮点不会也不致命但如果你准备的是大厂面试建议还是掌握。因为单调栈的应用范围很广不只是接雨水很多区间类问题都会用到。5.2 易错点汇总这些都是我踩过的坑第一个坑是忘记处理空数组。我一直强调力扣刷题第一行先判断边界if not height: return 0。尤其是用Python刷题时输入为[]的情况很容易被忽略而一旦忽略就会报索引错误。第二个坑是双指针的相等判断。当left_max right_max时走else分支移动右指针不会影响结果但有些同学会在这里纠结很久。我的建议是别纠结选一种写法跑一遍样例验证结果正确即可。力扣的判定只看最终值是否正确不看移动路径。第三个坑是单调栈的break条件。前面已经提到了栈弹出后为空说明左边没有墙无法积水必须跳出内层循环。少了这一句数组[3, 2, 1]这种纯递减场景就会算错。第四个坑是把下标和值搞混。单调栈存下标双指针存值。这个看似简单的区别在实际编码时非常容易搞乱。写单调栈时取高度一定要用height[stack[-1]]而不是stack[-1]。类似的错误我犯过好几次每次都得靠单元测试帮我揪出来。易错点错误示范正确做法空数组未处理直接访问height[0]先判断长度是否为0双指针等号不确定纠结不移动选一边移动即可结果不变单调栈break缺失栈空仍继续计算栈空说明无左墙break单调栈存值而非下标存value无法算宽度存下标宽度用索引差6. 从接雨水到一类题的解题框架6.1 同类题型的识别标志接雨水不是一道孤立的题它属于一个很典型的题型家族。这类题目的共同特点是数组本身代表某种高度或宽度需要你计算在这些约束条件下形成的“区域面积”或“可容纳量”。再看一遍题目特征你会发现它们有明显的识别标志——数组中存在“峰值”和“低谷”的相对关系计算结果与“较矮的一侧”有关。最典型的同类题就是力扣11题“盛最多水的容器”。那题简单一些只需要双指针从两端夹逼即可核心是移动较矮的一侧。力扣84题“柱状图中最大的矩形”则是单调栈的经典应用和接雨水的单调栈解法互为镜像——一个求存水一个求矩形面积栈的维护逻辑刚好相反。把这两道题对着刷你会对单调栈有脱胎换骨的理解。二维版本的接雨水力扣407题“接雨水 II”则是把一维的双指针/优先队列思想扩展到二维算是一个不错的进阶。我的建议是先刷完接雨水和柱状图最大矩形再去挑战二维版本不然挫败感会很强。6.2 刷题顺序与刻意练习建议如果你正在刷力扣热题100我建议你按这样的顺序来安排这几道题先做11题盛最多水的容器它是最简单的双指针入门题三分钟就能搞定再做42题接雨水用双指针解决它巩固移动较矮一侧的思维模型然后做84题柱状图中最大的矩形从中对比单调栈和接雨水在使用时的不同细节。这个顺序下来你会发现在做接雨水时积累的“较矮决定论”直觉在做容器题时只需要一次练习就能建立而84题会反过来帮你检验是否真正理解了单调栈中“弹出”的时机。还有一个实操建议刷完一道题后隔三天再重新默写一遍代码。尤其是接雨水这种思路多、细节多的题你会发现第一次写的时候觉得完全理解了隔几天再写还是会卡在某个边界条件上。这种“回生”是完全正常的恰恰说明你还没有把解法真正内化。多来几次“遗忘-重新理解”的过程这段代码才会彻底长在你脑子里。我在实际刷题中发现把双指针版本和单调栈版本都写到熟练之后再去写很多其他难题都会顺手得多。因为它们本质上训练的是同一件事如何在遍历过程中用最少的额外信息维护出解决问题所需的关键状态。这个能力远比记住某一道题的固定解法重要得多。
