从某一天开始我的刷题打卡日历上多了一条连续的第87天标记。那天我打开的每日一题恰好叫“挡住洪水”其实这道题在算法圈里还有更常见的名字接雨水或者直译过来的“存水量计算”。它问的不复杂给了你一排柱子高度下雨之后水会被柱子挡住多少。当时我盯着这个标题看了好一会儿不是因为题目本身有多绕而是因为我自己的刷题tracker记录里这已经是我第三次遇到同类型的水容量题了。前两次分别是二维版本和环形版本的变体最后一次才轮到这道经典题。这次我决定把从暴力解法到双指针优化的完整路径连同我在tracker里记录的踩坑复盘一起写下来。这篇内容适合所有刚开始刷每日一题、想系统整理自己成长路径的开发者也适合那些看到“接雨水”就头大想真正吃透这一类“看左右边界”几何题的人。1. 为什么我坚持给刷题配一个tracker每日一题才没有烂尾1.1 从收藏夹吃灰到打卡日历tracker到底解决了什么我见过太多人包括以前的自己刷题的方式是这样的今天兴致来了打开某个刷题平台从题目列表里随机挑一道做完AC了挺高兴明天忙了就断隔一周再打开发现之前看过的题已经完全眼生。这种刷法最大的问题不是量不够而是没有形成认知复利。后来我花了大概一个周末给自己搭了一个极简的刷题tracker做成一个Markdown表格放在本地仓库里。每天做完每日一题之后花三分钟更新一行记录。这个动作看起来不起眼但它把“我今天要不要刷题”这个决策从每天重新思考变成了“打开tracker看一眼昨天写的是什么按规律补上今天的”。启动成本被压得极低连续性自然就建立了。1.2 我的tracker字段设计和记录模板我不想搞得太复杂复杂的东西坚持不下来。我的打卡表只有这几列第几天题目标题难度核心考察标签是否一次AC大概耗时错误类型一句话复盘举个例子“挡住洪水”这一题我当时记录的模板大概是这样的第几天标题难度核心标签是否一次AC耗时错误类型一句话复盘87挡住洪水中等双指针/动态规划否28分钟边界更新双指针结算时机粗心矮侧先结算88某链表反转题变体中等链表是14分钟无递归思路比迭代好写但要注意栈深89某区间合并问题中等排序/扫描否22分钟边界特判没有考虑区间相接的情况这个表看起来简单但坚持三个月之后你回头翻能清楚地看到自己的薄弱点集中在哪一类错误上。比任何收藏夹都有用。1.3 复盘比刷量重要每周的固定回顾tracker不只是一个打卡本我更把它当作周报源数据。每周末我会看这一周的错误类型分布。如果一周内三次错误都出现在“边界条件”那下一周我就专门找边界条件多的题练。如果都是“思路正确但代码写错”那说明需要多写代码而不是多看题解。这个方法是我试过很多种刷题管理方案之后留下来的它没有多花什么时间却能让我对每日一题的投入真正变成可观察、可调整的进步过程。2. 挡住洪水这道题到底在算什么读懂题面比动代码更重要2.1 从题干到数学定义的一步翻译题目背景文字里通常会写一排宽度为1、高度不等的柱子立在水平地面上天降大雨后被柱子围出来的凹陷区域里能存住水要求计算总共能存多少单位体积的水。翻译成数组语言就是给你一个非负整数数组 heightheight[i] 表示第 i 根柱子的高度每根柱子的宽度都是 1。问这个地形能容纳的雨水总量。这里有一个特别容易被忽略的细节每根柱子的宽度是1。这意味着高度数组的数值直接对应单位面积数组长度多少无所谓每列的水量就是“水位的实际高度差”。如果你把宽度忽略掉后面计算单位会乱掉非要乘1也是白乘。2.2 手算一个标准例子搞清楚答案是哪来的我们拿最经典的用例来走一遍height [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]长度12我们一列一列看。每一列能存多少水取决于它左边所有柱子中最高的那一根和右边所有柱子中最高的那一根取这两者的较小值得到“这一列的理论水位”再用这个水位减去当前列自身的高度。如果结果是正数说明能存水如果是负数或者零说明存不了。逐列算一下下标从0开始第0列高0左侧最高0没有柱子右侧最高3min(0,3)-00第1列高1左最高1右最高3min-自身0第2列高0左最高1右最高3min-自身1第3列高2左最高2右最高3min-自身0第4列高1左最高2右最高3min-自身1第5列高0左最高2右最高3min-自身2第6列高1左最高2右最高3min-自身1第7列高3左最高3右最高3min-自身0第8列高2左最高3右最高2min-自身1第9列高1左最高3右最高2min-自身1第10列高2左最高3右最高2min-自身0第11列高1左最高3右最高1min-自身0把这些正数加起来1 1 2 1 1 1 6。所以答案是6。这个手算过程很啰嗦但它把题目彻底拆透了。2.3 常见理解偏差不是水位线也不是最大矩形我见过不少人把这道题理解成“找到最高水位线”或者“求最大能盛水的矩形面积”这都不对。这道题的核心是“每个位置独立结算存水量然后累加”不是找一个整体容器。老实说第一次做的时候我也在“最高水位”和“逐列水量”之间犹豫了一阵最后靠手算例子才发现自己想岔了。读题这一关过不去后面的所有优化代码都是空中楼阁。3. 先写暴力再谈优化逐列累积的O(n²)写法3.1 暴力解为什么值得写一遍不少刷题新手有个误区觉得面试或者每日一题就是要一上来写出最优解。实际上自己先写出一个逻辑正确但时间复杂度差的解法比直接背最优解有价值得多。原因很简单暴力解能让你确认自己对题意的理解是对的同时给后续优化提供清晰的思路起点。对于这道题暴力解的思路极其直接遍历每个位置 i从 0 到 i-1 扫一遍找左侧最高柱子的高度再从 i1 到 n-1 扫一遍找右侧最高柱子的高度然后用 min(左最高, 右最高) - height[i] 计算当前列能存的水负值就当作 0累加到结果里。3.2 暴力代码与逐行走读用Python写出来大概是这样的def trap_bruteforce(height): n len(height) total 0 for i in range(n): left_max 0 right_max 0 # 找左侧最高 for j in range(i 1): left_max max(left_max, height[j]) # 找右侧最高 for j in range(i, n): right_max max(right_max, height[j]) water min(left_max, right_max) - height[i] if water 0: total water return total注意两个细节左侧扫描要从 0 扫到 i右侧扫描要从 i 扫到 n-1这样当前位置自身的高度也包含在“最高峰”里。因为水位不会低于当前位置的高度如果自身就是当前区间最高那这一列存水量是0符合直觉。复杂度也很好算外层循环 n 次每次内层两个循环各扫最多 n 步总时间复杂度 O(n²)。空间复杂度 O(1)只用了个别变量。3.3 暴力的价值它是你验证所有优化版本的基准我实际写这道题的时候先写了暴力版本然后写了一个随机测试脚本生成几百组随机数组拿暴力版本的结果当基准对比后面DP版本和双指针版本的结果。三者全部一致才敢说代码没问题。这个习惯帮我抓出过不止一次对拍错误也让我在写复杂解法的时候心里踏实。暴力的另一个用途是面试时的沟通策略。代码简单到面试官一听就懂就能把接下来大部分时间花在讲“为什么要优化”上。这是从“能刷题”到“会解题”的分水岭。4. 空间换时间用两个峰值数组把复杂度压到O(n)4.1 状态定义与递推关系观察暴力解法你会发现每个位置都重复计算了左侧最高和右侧最高。我们能不能先把所有位置的左侧最高和右侧最高提前算好后面直接查表这就是这题最常见的动态规划优化。定义两个数组left_max[i]从下标0到i范围内最高的柱子高度right_max[i]从下标i到数组末尾范围内最高的柱子高度它们有很清晰的递推关系left_max[i] max(left_max[i-1], height[i])right_max[i] max(right_max[i1], height[i])这两个递推式非常规整本质上就是“从左往右做前缀最大值”和“从右往左做后缀最大值”。4.2 三道循环的完整代码def trap_dp(height): n len(height) if n 0: 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]) total 0 for i in range(n): water min(left_max[i], right_max[i]) - height[i] if water 0: total water return total三个循环各自都是O(n)总时间复杂度是O(n)。空间上多了两个长度为n的数组空间复杂度O(n)。这里有个边界处理很容易写错数组为空的时候left_max[0]这种写法会直接越界。我在tracker里记的第一次提交错误就是漏了n0的特判平台给我报了个数组越界错误。所以一旦你准备用下标访问第0个元素先想清楚数组有没有可能是空的。4.3 为什么左右峰值数组是经典的动态规划思路说白了这个问题的子问题结构是每个位置存水量只依赖两个量——左侧历史最大值和右侧未来最大值。而这两个量本身又有重叠的计算结构left_max[i]依赖left_max[i-1]right_max[i]依赖right_max[i1]。如果你在面试里已经写出了暴力版本下一步顺理成章就是告诉面试官我们发现重复计算了那就把重复计算的结果缓存起来。这是空间换时间最典型的应用场景也是动态规划中的“记忆化”思想在这类数组题里的体现。我个人的体会是很多人不是不会写DP而是不会从一个暴力代码里看出“哪些计算是重复的”。多练几次这种“暴力转缓存”的路径比单独背多少种DP模板都有用。5. 双指针一次遍历省掉数组还能顺手把逻辑简化5.1 省空间的直觉哪边矮就先结算哪边现在我们已经有了O(n)时间和O(n)空间的解法但面试题常常还会追问一句能不能不用额外数组答案就是双指针。这题的双指针不是那种维护窗口的常规用法而是一种比较精巧的单调收缩思路。核心观察是对于最左边的柱子它的水位只取决于左侧已经遇到过的最高柱子和右侧某个位置上的高柱子。如果左侧的某个最高峰比右侧当前遇到的最高峰矮那左指针当前位置的水位已经被左侧这个矮高峰决定了而不需要知道右侧更远处到底有多高。反过来也一样。这就是为什么可以把问题拆成“哪边矮先结算哪边”然后不断向中间收拢。5.2 双指针代码def trap_two_pointer(height): n len(height) if n 0: return 0 left 0 right n - 1 left_max 0 right_max 0 total 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: total left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: total right_max - height[right] right - 1 return total我们拿一个短数组手推一遍通常我用 [3, 0, 0, 2, 0, 4] 来验证答案是10。初始 left0, right5height[0]3height[5]4。左边比右边矮处理左侧height[0] left_max(0)所以更新 left_max3left1height[1]0height[5]4处理左侧0小于left_max(3)累加 3。total3left2height[2]0处理左侧累加3total6left3height[3]2处理左侧累加 left_max - 2 1total7left4height[4]0处理左侧累加3total10left5leftright循环结束。5.3 双指针踩过的坑更新时机和移动时机这个解法我第一次写的时候虽然思路已经懂了但还是在两个地方翻了车。第一个坑是更新最大值和累加水量的顺序。你要先判断当前柱子和已记录的最高峰之间的大小关系如果当前柱子比历史最高峰还高说明它是新的左边界不能算水只能更新 left_max如果当前柱子比历史最高峰矮那这个坑洼处能存的水就是两者之差。这个判断顺序写反了结果就会差得很离谱。第二个坑是移动指针的时机。很多人喜欢在结算完一个位置之后先更新最大值再移动这没问题但有人会在更新最大值之后忘记移动指针导致死循环。我在实际练习里养成一个习惯每个分支处理完立刻写一步 left 1 或 right - 1让指针移动成为这个分支的固定收尾动作就不会漏了。双指针解法的时间复杂度是O(n)空间复杂度是O(1)既没有额外数组也没有重复扫描是目前这道题最优的常数额定解法。实际跑起来比DP版本要快不少。6. 这题的周边变体以及我在tracker里的复盘记录6.1 我第一次提交就失败的完整记录这道题在tracker里留给我的最有价值的东西不是最后的AC结果而是第一次提交失败的记录。我当时的思路是双指针但我在“结算哪边”上写反了我每次选择让左边走但其实应该看当前左右柱子哪个矮。为什么写反了因为我潜意识里把“左边先动”当成了惯例。这类惯性思维在实战题里非常致命。后来我把这个错误记成一句话双指针不是左指针优先而是矮边界优先。之后再遇到任何类似“看两侧决定哪边走”的题我都会先问一句当前应该动哪一边。6.2 变体和面试延伸从一维到二维“挡住洪水”/接雨水这一题还有几个很常见的变体我建议刷每日一题时顺带了解一下二维版本给一个二维矩阵每个格子有高度求整个二维地形能接住的水量。这个题的思路核心从“看左右”变成了“从边界向中心BFS/用堆维护最低边界”难度直接上一个台阶。环形版本柱子围成一圈左右边界相连。解法基本沿袭双指针思路但要注意首尾相接的处理。水淹岛屿类问题本质上是反过来的水容量问题判断哪些低洼区域会被淹没。面试官也很喜欢把“接雨水”当一个引子让你先写出双指针然后追问“二维怎么做”“如果边界不是封闭的会怎样”。所以吃透这题等于掌握了一套“边界决定水位”的思考框架比单纯记代码有用得多。6.3 三种解法对比与选型建议我习惯在tracker的周复盘里做一个小表格把同类题的解法放在一起对比解法时间复杂度空间复杂度适用场景暴力逐列O(n²)O(1)验证思路、小数据量对拍动态规划/预计算O(n)O(n)思路清晰面试中作为中间过渡双指针O(n)O(1)最优解面试首选代码细节多单调栈O(n)O(n)适合扩展边界场景维护结构直观如果你面试时间充裕我建议的路径是先说暴力思路再说DP预计算最后给出双指针。这样面试官能看到你在有意识地进行复杂度的递进优化而不是直接背答案。在实际笔试中没有时间压力的话直接写双指针时间紧但怕边界出错DP版本反而更不容易写错是一个不错的保底选择。最后再分享一个小技巧这题做完之后我在tracker里的“一句话复盘”写的是“矮边界先结算”这几个字在几周之后又帮我解决了一道二维接雨水的边界选择问题。每天只刷一题只要每题都留下这样一句能触发回忆的复盘语积累半年你的解题直觉会比你想象的好得多。 
长河君 · 2026/10/14 5:43:32 · 阅读 1.2k 每日一题接雨水：从暴力到双指针的优化之路
从某一天开始我的刷题打卡日历上多了一条连续的第87天标记。那天我打开的每日一题恰好叫“挡住洪水”其实这道题在算法圈里还有更常见的名字接雨水或者直译过来的“存水量计算”。它问的不复杂给了你一排柱子高度下雨之后水会被柱子挡住多少。当时我盯着这个标题看了好一会儿不是因为题目本身有多绕而是因为我自己的刷题tracker记录里这已经是我第三次遇到同类型的水容量题了。前两次分别是二维版本和环形版本的变体最后一次才轮到这道经典题。这次我决定把从暴力解法到双指针优化的完整路径连同我在tracker里记录的踩坑复盘一起写下来。这篇内容适合所有刚开始刷每日一题、想系统整理自己成长路径的开发者也适合那些看到“接雨水”就头大想真正吃透这一类“看左右边界”几何题的人。1. 为什么我坚持给刷题配一个tracker每日一题才没有烂尾1.1 从收藏夹吃灰到打卡日历tracker到底解决了什么我见过太多人包括以前的自己刷题的方式是这样的今天兴致来了打开某个刷题平台从题目列表里随机挑一道做完AC了挺高兴明天忙了就断隔一周再打开发现之前看过的题已经完全眼生。这种刷法最大的问题不是量不够而是没有形成认知复利。后来我花了大概一个周末给自己搭了一个极简的刷题tracker做成一个Markdown表格放在本地仓库里。每天做完每日一题之后花三分钟更新一行记录。这个动作看起来不起眼但它把“我今天要不要刷题”这个决策从每天重新思考变成了“打开tracker看一眼昨天写的是什么按规律补上今天的”。启动成本被压得极低连续性自然就建立了。1.2 我的tracker字段设计和记录模板我不想搞得太复杂复杂的东西坚持不下来。我的打卡表只有这几列第几天题目标题难度核心考察标签是否一次AC大概耗时错误类型一句话复盘举个例子“挡住洪水”这一题我当时记录的模板大概是这样的第几天标题难度核心标签是否一次AC耗时错误类型一句话复盘87挡住洪水中等双指针/动态规划否28分钟边界更新双指针结算时机粗心矮侧先结算88某链表反转题变体中等链表是14分钟无递归思路比迭代好写但要注意栈深89某区间合并问题中等排序/扫描否22分钟边界特判没有考虑区间相接的情况这个表看起来简单但坚持三个月之后你回头翻能清楚地看到自己的薄弱点集中在哪一类错误上。比任何收藏夹都有用。1.3 复盘比刷量重要每周的固定回顾tracker不只是一个打卡本我更把它当作周报源数据。每周末我会看这一周的错误类型分布。如果一周内三次错误都出现在“边界条件”那下一周我就专门找边界条件多的题练。如果都是“思路正确但代码写错”那说明需要多写代码而不是多看题解。这个方法是我试过很多种刷题管理方案之后留下来的它没有多花什么时间却能让我对每日一题的投入真正变成可观察、可调整的进步过程。2. 挡住洪水这道题到底在算什么读懂题面比动代码更重要2.1 从题干到数学定义的一步翻译题目背景文字里通常会写一排宽度为1、高度不等的柱子立在水平地面上天降大雨后被柱子围出来的凹陷区域里能存住水要求计算总共能存多少单位体积的水。翻译成数组语言就是给你一个非负整数数组 heightheight[i] 表示第 i 根柱子的高度每根柱子的宽度都是 1。问这个地形能容纳的雨水总量。这里有一个特别容易被忽略的细节每根柱子的宽度是1。这意味着高度数组的数值直接对应单位面积数组长度多少无所谓每列的水量就是“水位的实际高度差”。如果你把宽度忽略掉后面计算单位会乱掉非要乘1也是白乘。2.2 手算一个标准例子搞清楚答案是哪来的我们拿最经典的用例来走一遍height [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]长度12我们一列一列看。每一列能存多少水取决于它左边所有柱子中最高的那一根和右边所有柱子中最高的那一根取这两者的较小值得到“这一列的理论水位”再用这个水位减去当前列自身的高度。如果结果是正数说明能存水如果是负数或者零说明存不了。逐列算一下下标从0开始第0列高0左侧最高0没有柱子右侧最高3min(0,3)-00第1列高1左最高1右最高3min-自身0第2列高0左最高1右最高3min-自身1第3列高2左最高2右最高3min-自身0第4列高1左最高2右最高3min-自身1第5列高0左最高2右最高3min-自身2第6列高1左最高2右最高3min-自身1第7列高3左最高3右最高3min-自身0第8列高2左最高3右最高2min-自身1第9列高1左最高3右最高2min-自身1第10列高2左最高3右最高2min-自身0第11列高1左最高3右最高1min-自身0把这些正数加起来1 1 2 1 1 1 6。所以答案是6。这个手算过程很啰嗦但它把题目彻底拆透了。2.3 常见理解偏差不是水位线也不是最大矩形我见过不少人把这道题理解成“找到最高水位线”或者“求最大能盛水的矩形面积”这都不对。这道题的核心是“每个位置独立结算存水量然后累加”不是找一个整体容器。老实说第一次做的时候我也在“最高水位”和“逐列水量”之间犹豫了一阵最后靠手算例子才发现自己想岔了。读题这一关过不去后面的所有优化代码都是空中楼阁。3. 先写暴力再谈优化逐列累积的O(n²)写法3.1 暴力解为什么值得写一遍不少刷题新手有个误区觉得面试或者每日一题就是要一上来写出最优解。实际上自己先写出一个逻辑正确但时间复杂度差的解法比直接背最优解有价值得多。原因很简单暴力解能让你确认自己对题意的理解是对的同时给后续优化提供清晰的思路起点。对于这道题暴力解的思路极其直接遍历每个位置 i从 0 到 i-1 扫一遍找左侧最高柱子的高度再从 i1 到 n-1 扫一遍找右侧最高柱子的高度然后用 min(左最高, 右最高) - height[i] 计算当前列能存的水负值就当作 0累加到结果里。3.2 暴力代码与逐行走读用Python写出来大概是这样的def trap_bruteforce(height): n len(height) total 0 for i in range(n): left_max 0 right_max 0 # 找左侧最高 for j in range(i 1): left_max max(left_max, height[j]) # 找右侧最高 for j in range(i, n): right_max max(right_max, height[j]) water min(left_max, right_max) - height[i] if water 0: total water return total注意两个细节左侧扫描要从 0 扫到 i右侧扫描要从 i 扫到 n-1这样当前位置自身的高度也包含在“最高峰”里。因为水位不会低于当前位置的高度如果自身就是当前区间最高那这一列存水量是0符合直觉。复杂度也很好算外层循环 n 次每次内层两个循环各扫最多 n 步总时间复杂度 O(n²)。空间复杂度 O(1)只用了个别变量。3.3 暴力的价值它是你验证所有优化版本的基准我实际写这道题的时候先写了暴力版本然后写了一个随机测试脚本生成几百组随机数组拿暴力版本的结果当基准对比后面DP版本和双指针版本的结果。三者全部一致才敢说代码没问题。这个习惯帮我抓出过不止一次对拍错误也让我在写复杂解法的时候心里踏实。暴力的另一个用途是面试时的沟通策略。代码简单到面试官一听就懂就能把接下来大部分时间花在讲“为什么要优化”上。这是从“能刷题”到“会解题”的分水岭。4. 空间换时间用两个峰值数组把复杂度压到O(n)4.1 状态定义与递推关系观察暴力解法你会发现每个位置都重复计算了左侧最高和右侧最高。我们能不能先把所有位置的左侧最高和右侧最高提前算好后面直接查表这就是这题最常见的动态规划优化。定义两个数组left_max[i]从下标0到i范围内最高的柱子高度right_max[i]从下标i到数组末尾范围内最高的柱子高度它们有很清晰的递推关系left_max[i] max(left_max[i-1], height[i])right_max[i] max(right_max[i1], height[i])这两个递推式非常规整本质上就是“从左往右做前缀最大值”和“从右往左做后缀最大值”。4.2 三道循环的完整代码def trap_dp(height): n len(height) if n 0: 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]) total 0 for i in range(n): water min(left_max[i], right_max[i]) - height[i] if water 0: total water return total三个循环各自都是O(n)总时间复杂度是O(n)。空间上多了两个长度为n的数组空间复杂度O(n)。这里有个边界处理很容易写错数组为空的时候left_max[0]这种写法会直接越界。我在tracker里记的第一次提交错误就是漏了n0的特判平台给我报了个数组越界错误。所以一旦你准备用下标访问第0个元素先想清楚数组有没有可能是空的。4.3 为什么左右峰值数组是经典的动态规划思路说白了这个问题的子问题结构是每个位置存水量只依赖两个量——左侧历史最大值和右侧未来最大值。而这两个量本身又有重叠的计算结构left_max[i]依赖left_max[i-1]right_max[i]依赖right_max[i1]。如果你在面试里已经写出了暴力版本下一步顺理成章就是告诉面试官我们发现重复计算了那就把重复计算的结果缓存起来。这是空间换时间最典型的应用场景也是动态规划中的“记忆化”思想在这类数组题里的体现。我个人的体会是很多人不是不会写DP而是不会从一个暴力代码里看出“哪些计算是重复的”。多练几次这种“暴力转缓存”的路径比单独背多少种DP模板都有用。5. 双指针一次遍历省掉数组还能顺手把逻辑简化5.1 省空间的直觉哪边矮就先结算哪边现在我们已经有了O(n)时间和O(n)空间的解法但面试题常常还会追问一句能不能不用额外数组答案就是双指针。这题的双指针不是那种维护窗口的常规用法而是一种比较精巧的单调收缩思路。核心观察是对于最左边的柱子它的水位只取决于左侧已经遇到过的最高柱子和右侧某个位置上的高柱子。如果左侧的某个最高峰比右侧当前遇到的最高峰矮那左指针当前位置的水位已经被左侧这个矮高峰决定了而不需要知道右侧更远处到底有多高。反过来也一样。这就是为什么可以把问题拆成“哪边矮先结算哪边”然后不断向中间收拢。5.2 双指针代码def trap_two_pointer(height): n len(height) if n 0: return 0 left 0 right n - 1 left_max 0 right_max 0 total 0 while left right: if height[left] height[right]: if height[left] left_max: left_max height[left] else: total left_max - height[left] left 1 else: if height[right] right_max: right_max height[right] else: total right_max - height[right] right - 1 return total我们拿一个短数组手推一遍通常我用 [3, 0, 0, 2, 0, 4] 来验证答案是10。初始 left0, right5height[0]3height[5]4。左边比右边矮处理左侧height[0] left_max(0)所以更新 left_max3left1height[1]0height[5]4处理左侧0小于left_max(3)累加 3。total3left2height[2]0处理左侧累加3total6left3height[3]2处理左侧累加 left_max - 2 1total7left4height[4]0处理左侧累加3total10left5leftright循环结束。5.3 双指针踩过的坑更新时机和移动时机这个解法我第一次写的时候虽然思路已经懂了但还是在两个地方翻了车。第一个坑是更新最大值和累加水量的顺序。你要先判断当前柱子和已记录的最高峰之间的大小关系如果当前柱子比历史最高峰还高说明它是新的左边界不能算水只能更新 left_max如果当前柱子比历史最高峰矮那这个坑洼处能存的水就是两者之差。这个判断顺序写反了结果就会差得很离谱。第二个坑是移动指针的时机。很多人喜欢在结算完一个位置之后先更新最大值再移动这没问题但有人会在更新最大值之后忘记移动指针导致死循环。我在实际练习里养成一个习惯每个分支处理完立刻写一步 left 1 或 right - 1让指针移动成为这个分支的固定收尾动作就不会漏了。双指针解法的时间复杂度是O(n)空间复杂度是O(1)既没有额外数组也没有重复扫描是目前这道题最优的常数额定解法。实际跑起来比DP版本要快不少。6. 这题的周边变体以及我在tracker里的复盘记录6.1 我第一次提交就失败的完整记录这道题在tracker里留给我的最有价值的东西不是最后的AC结果而是第一次提交失败的记录。我当时的思路是双指针但我在“结算哪边”上写反了我每次选择让左边走但其实应该看当前左右柱子哪个矮。为什么写反了因为我潜意识里把“左边先动”当成了惯例。这类惯性思维在实战题里非常致命。后来我把这个错误记成一句话双指针不是左指针优先而是矮边界优先。之后再遇到任何类似“看两侧决定哪边走”的题我都会先问一句当前应该动哪一边。6.2 变体和面试延伸从一维到二维“挡住洪水”/接雨水这一题还有几个很常见的变体我建议刷每日一题时顺带了解一下二维版本给一个二维矩阵每个格子有高度求整个二维地形能接住的水量。这个题的思路核心从“看左右”变成了“从边界向中心BFS/用堆维护最低边界”难度直接上一个台阶。环形版本柱子围成一圈左右边界相连。解法基本沿袭双指针思路但要注意首尾相接的处理。水淹岛屿类问题本质上是反过来的水容量问题判断哪些低洼区域会被淹没。面试官也很喜欢把“接雨水”当一个引子让你先写出双指针然后追问“二维怎么做”“如果边界不是封闭的会怎样”。所以吃透这题等于掌握了一套“边界决定水位”的思考框架比单纯记代码有用得多。6.3 三种解法对比与选型建议我习惯在tracker的周复盘里做一个小表格把同类题的解法放在一起对比解法时间复杂度空间复杂度适用场景暴力逐列O(n²)O(1)验证思路、小数据量对拍动态规划/预计算O(n)O(n)思路清晰面试中作为中间过渡双指针O(n)O(1)最优解面试首选代码细节多单调栈O(n)O(n)适合扩展边界场景维护结构直观如果你面试时间充裕我建议的路径是先说暴力思路再说DP预计算最后给出双指针。这样面试官能看到你在有意识地进行复杂度的递进优化而不是直接背答案。在实际笔试中没有时间压力的话直接写双指针时间紧但怕边界出错DP版本反而更不容易写错是一个不错的保底选择。最后再分享一个小技巧这题做完之后我在tracker里的“一句话复盘”写的是“矮边界先结算”这几个字在几周之后又帮我解决了一道二维接雨水的边界选择问题。每天只刷一题只要每题都留下这样一句能触发回忆的复盘语积累半年你的解题直觉会比你想象的好得多。