企业官网建设流程全解析

LeetCode 42 这道题，圈内叫"接雨水"，面试出场率有多高不用我多说。几乎所有准备过大厂算法面试的人都刷过它，但说实话，能把这道题从暴力解法一路讲到双指针最优解、并且让面试官点头的人，真不多。很多人记住了代码模板，却说不清"为什么左指针移动时能确定右边一定有足够的墙"。这篇就按我自己的理解路径来拆，从最笨的解法开始，一步步推到最优解，再把单调栈这个备胎方案也讲透。

先说这道题是什么。给定 n 个非负整数表示宽度为 1 的柱子的高度图，计算按此排列的柱子下雨后能接多少雨水。height = [0,1,0,2,1,0,1,3,2,1,2,1]，答案是 6。核心就一句话：每个位置能存多少水，取决于它左边最高柱子和右边最高柱子中较矮的那一个，再减去当前位置的高度。这个认知是整个问题的钥匙。

这篇文章适合三类人：第一类是刚刷题不久的新手，需要有人把思路掰开揉碎讲清楚；第二类是刷过但老忘、面试前想快速捡起来的同学；第三类是准备讲这道题给别人听的，需要理解每个解法背后的动机，而不是死记硬背。不管你是哪一类，读完你应该能徒手写出最优解，并且能应对面试官的各种追问。

1. 题目解读与核心矛盾拆解

1.1 接雨水的物理直觉：每个凹槽的水位线

先建立一个物理模型。把柱子想象成一排高低不一的墙，下雨后水会积在凹陷处。问题是：每个位置上方能不能存水、能存多少，取决于什么？

关键在于"水往低处流"这个直觉的反面——水并不是简单地往低处流，它最终会稳定在某个水平面上。对于位置 i 来说，如果这个位置的高度是 height[i]，它能存水的条件是：左右两侧都存在比 height[i] 更高的柱子。存水量 = min(左侧最高高度, 右侧最高高度) - height[i]。

为什么要取左右最大值的较小者？因为水是流体，它不会越过最矮的那堵墙。这就好比两个水库之间的水，水位永远由较低那个坝顶决定。你可以想象一个极端情况：左边有一座 100 米的高墙，右边只有一座 3 米的矮墙，中间某个凹槽高度为 1 米，那这个凹槽里的水最多只能存到 2 米——因为超过 3 米，水就从右边流走了。

这个公式就是全部。整道题的所有解法，本质上都是在回答同一个问题：如何高效地知道每个位置左边和右边的最大高度？

1.2 为什么这道题是面试高频题

我个人判断，这道题之所以被各大厂反复翻牌子，有三个原因。

第一，它考察的是"建模能力"。题目描述是生活化的，但需要你抽象成数学公式，这个从具体到抽象的过程本身就是面试想看的。

第二，它有明显的复杂度梯度。暴力 O(n²) 能写，动态规划 O(n) 时间和 O(n) 空间能写，双指针 O(n) 时间 O(1) 空间也能写。面试官可以通过追问"能不能优化空间"来判断你的水平。

第三，它和另一道经典题"盛最多水的容器"形成对照。两道题一字之差，思路却是两个方向：盛水容器是找两条柱子围成的面积，向内收缩时移动较短的那根；接雨水是统计每个位置能存的水量，双指针移动时移动较矮的那侧。能讲清楚这两者的区别，说明你是真理解了双指针的本质。

2. 暴力解法：先懂公式，再谈优化

2.1 逐列计算：最直白的实现

最笨但也最能验证公式正确性的办法是：遍历每个位置 i，分别向左扫描找最大值 maxLeft，向右扫描找最大值 maxRight，然后取 min(maxLeft, maxRight) - height[i]，如果结果是正数就累加。

def trap_brute_force(height): n = len(height) total = 0 for i in range(n): max_left = 0 for j in range(i - 1, -1, -1): max_left = max(max_left, height[j]) max_right = 0 for j in range(i + 1, n): max_right = max(max_right, height[j]) water = min(max_left, max_right) - height[i] if water > 0: total += water return total

注意两个细节。第一，计算 max_left 时要从 i-1 开始往左走，不包含自己，因为自己不能挡自己的水。第二，边界位置 i=0 和 i=n-1 必然接不到水，因为有一侧没有墙，所以 min(maxLeft, maxRight) 必然是 0，结果自然为 0，不需要特判。

这个解法的时间复杂度是 O(n²)，空间 O(1)。n 小的时候能跑，但面试官看到这个解法一般会点点头，然后问一句："能不能快一点？"

2.2 从暴力到动态规划：空间换时间的自然演进

暴力的浪费在于：每个位置都要重新向左扫描一遍，但很多扫描是重复的。位置 i 的 maxLeft 明明可以由位置 i-1 的 maxLeft 递推得到：maxLeft[i] = max(maxLeft[i-1], height[i-1])。

这就是动态规划的思路。开两个数组，leftMax 和 rightMax，先各扫一遍预处理，然后遍历一次计算答案。

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): total += min(left_max[i], right_max[i]) - height[i] return total

这里有个细节和暴力法不同：leftMax[i] 包含了自己，因为后面计算 min(leftMax[i], rightMax[i]) - height[i] 时，如果自己就是左侧最高的，那 leftMax[i] == height[i]，水就是 0，逻辑上等价且更简洁。包含自己可以避免数组边界特判，这是写动态规划时常见的小技巧——用初始化值替代条件判断。

时间复杂度 O(n)，空间 O(n)。这个版本一般能过面试，但如果面试官要求 O(1) 空间，就得继续往下想了。

2.3 面试现场：从 DP 到双指针的心理博弈

我想聊一下面试时的节奏。大多数人能写出 DP 解，但面试官的期待往往是你能直接跳到双指针。这时候别慌，也不用假装自己一开始就会最优解，可以说："我想一下怎么省掉这两个数组。其实我们并不需要知道每个位置左右最大值是多少，只需要在移动的过程中维护一个当前看到的最大值。"

这个思路的转折点是：为什么需要两个数组？因为我们计算位置 i 的存水量时，需要同时知道左右两侧的最大值。但如果我能保证右边一定有一个柱子比左边当前最大值更高，那我根本不需要知道右侧最大值具体是多少——右侧最大值至少是左边这个值，min 的结果就是左边最大值。

怎么保证？答案是：同时从左右两端往中间遍历，每次都移动"较矮"的那一侧。让右侧先遇到一个比左侧当前最大值更高的柱子，或者左侧先遇到一个比右侧当前最大值更高的柱子，取决于哪边矮。这个逻辑下面展开讲。

3. 双指针解法：最优解的核心逻辑

3.1 移动矮指针的深层原理

双指针的代码很简短，但理解它的人和不理解它的人写出来，应对追问的能力完全不同。

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

核心逻辑是：left_max 记录的是从最左到 left 位置见过的最大值，right_max 记录的是从最右到 right 位置见过的最大值。

当 height[left] < height[right] 时，说明 left 这一侧的墙比右侧当前指向的墙矮。此时，对于位置 left 来说，它的右侧最大值至少是 height[right]，而它的左侧最大值是 left_max。如果我让 left_max 小于等于 height[right]，那 min(left_max, right_max) 就等于 left_max，也就是说——位置 left 的存水量只由 left_max 决定，不需要管右侧还有没有更高的墙。

为什么可以这样断言？因为 right 指针右侧的墙，我们已经见过了 right_max，而 right_max ≥ height[right] > height[left]。左侧最大值 left_max 就算再怎么大，它在 min 里顶多等于 height[right] 这个量级。换句话说，右边界"兜底"的墙已经出现在眼前了，左侧的矮柱子能存多少水，只看它见过的左边最高墙就够了。

这个逻辑我当初绕了很久才转过来。画个图就清楚了：想象 right 指针站在一个比较高的柱子上，left 指针站在一个矮柱子上。对于 left 这个位置，右边已经确认有一个不低于 right 柱子的墙，水不可能从右边漏掉，所以水量完全取决于左边。既然 right 那边的情况不影响结果，我们就可以安心处理 left，然后把它往右移。

3.2 代码逐行拆解与边界推演

把上面的代码拆开看每一行。

当进入if height[left] < height[right]分支时，left_max 更新逻辑是：先判断当前柱子是否比之前见过的最高柱子还高。如果是，更新 left_max——因为高柱子本身不会存水；如果不是，说明当前位置处于一个凹槽里，左右都有高于它的墙，存水量是 left_max - height[left]。

有人会问：left_max 是左侧最大值，它一定大于 height[left] 吗？不一定。但是在height[left] < left_max这个分支里，我们能进来就说明if height[left] >= left_max为 False，也就是 height[left] < left_max，所以 left_max - height[left] 一定为正，不需要再和 0 比较。

这个细节特别重要。很多初学版本会在累加时写total += max(0, left_max - height[left])，但其实在算法逻辑保证下这个 max(0, ...) 是多余的。写出来不扣分，但能意识到"不需要判断"说明你真的理解了代码里隐含的不变量。

右指针的对称逻辑完全一样：当 height[right] <= height[left] 时，右侧最大值 right_max 决定了位置 right 的存水量。注意这里用的是else，也就是左右相等时走右指针分支，这没有影响，因为高度相等时处理哪边都对，水量计算结果是 0。

3.3 为什么不需要担心"漏算"中间的柱子

我第一次看双指针解法时最大的疑惑是：每次只处理 left 或 right 中的一个位置，中间那些还没遍历到的位置怎么办？

答案是：每个位置被处理且仅被处理一次。left 从左往右走，每走一步就处理一个位置；right 从右往左走，每走一步也处理一个位置。当 left 和 right 相遇时，所有中间位置都被处理过了。最后相遇的那个位置不用处理，因为它已经被某一侧的指针处理过了，或者它就是两侧最高柱子的交界处，存水量一定为 0。

用具体的例子推一遍。height = [0,1,0,2,1,0,1,3,2,1,2,1]，left=0，right=11。height[0]=0 < height[11]=1，进入左分支，left_max 更新为 0，total += 0。left=1。height[1]=1 < height[11]=1 不成立，进入右分支，right_max 更新为 1，right=10。height[10]=2，此时 left=1，height[1]=1 < 2，左分支，left_max 从 0 更新为 1，因为 height[1] >= left_max。left=2。height[2]=0 < height[10]=2，左分支，0 < left_max=1，total += 1 - 0 = 1。这是第一格水。后面继续推，总共得到 6 格水。

这个例子建议自己动手推一遍，感受指针移动时"哪边矮就把哪边吃掉"的节奏。

3.4 复杂度分析与最优性证明

双指针解法的时间复杂度是 O(n)，因为 left 和 right 总共移动 n-1 次；空间复杂度 O(1)，只用了两个变量。这是这道题的最优解，时间复杂度上不可能低于 O(n)，因为你至少要看一遍所有柱子才能知道它们的高度。

空间上也不可能低于 O(1)，因为你只需要两个指针和两个最大值变量。理论上比 O(1) 更小的空间不存在，所以这就是最优。面试官问"还能优化吗"的时候，有底气地告诉他：不能了，时间和空间都已经是下界。

4. 单调栈解法：另一种武器的完整解析

4.1 用栈维护"下降序列"：按行接水的思路

双指针法本质上是"按列"计算每个位置的积水量，单调栈法则是"按层"计算。它维护一个栈，栈内柱子的高度保持单调递减（从栈底到栈顶）。当新柱子比栈顶高时，说明出现了凹槽——栈顶是最低点，它两侧分别是新柱子和栈内前一个柱子，这三者围成了一个储水区间。

单调栈处理的逻辑是：遇到一个比栈顶高的柱子，弹出栈顶作为凹槽底部，此时凹槽的宽度是新柱子下标与栈内新栈顶下标之间的距离减 1，高度是 min(两侧柱子高度) - 凹槽底部高度，两者相乘就是这一层的积水量。

def trap_stack(height): n = len(height) stack = [] total = 0 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 h = min(height[left], height[i]) - height[bottom] total += width * h stack.append(i) return total

这个解法的关键理解点有两个。第一，为什么是while而不是if：因为弹出一个凹槽后，新栈顶可能仍然小于当前柱子，说明还能继续形成新的凹槽，要一直弹到栈顶高于当前柱子或者栈空为止。

第二，为什么弹出后要检查栈是否为空：如果栈为空，说明弹出的柱子左边没有更高的墙了，水会从左边流走，接不住水，直接 break。

4.2 单调栈的宽度计算：最容易写错的地方

我见过太多人在宽度计算这里翻车。width 不是 1，而是 i - left - 1。举例说明，height = [2, 0, 1]，i=2 时，height[2]=1 > height[1]=0，弹出 bottom=1，此时栈内剩 left=0，height[0]=2。width = 2 - 0 - 1 = 1，高度 = min(2, 1) - 0 = 1，积水量 = 1。对，就一格水，夹在 2 和 1 中间的凹槽。

再看 height = [2, 0, 0, 1]，i=3 时，弹出 bottom=2（柱子高度 0），栈内 left=0，height[0]=2。width = 3 - 0 - 1 = 2，高度 = min(2, 1) - 0 = 1，积水量 = 2——两格水，因为凹槽底部是连续两个 0，宽度为 2。

这就是"按层"计算的直观体现：每次弹出的只是一个"层"的高度，宽度由两个更高的柱子之间的距离决定。整个算法会多次弹出同一个区域的不同高度层，比如一个深凹槽，可能先弹出浅层再弹出深层。我建议你拿 height = [5,2,1,2,5] 手动模拟一次，你会看到栈是怎么一层一层剥出水的。这个例子中，i=3 时弹出 height=1 的柱子，计算一层水；i=4 时弹出 height=2 的柱子，又计算一层水，两层水合计起来就是完整的凹槽积水量。

4.3 双指针 vs 单调栈：面试时怎么选

两种解法的对比，我放在一张表里。

我的建议是：面试首选双指针，因为它常数小、空间省、代码简洁。但如果面试官追问"还有别的方法吗"，单调栈就能派上用场——能写出单调栈解法往往给人留下"底子扎实"的印象。而且单调栈解法对理解后面"柱状图中最大的矩形"（LeetCode 84）有直接帮助，那道题是单调栈的经典应用，两题放在一起学效率很高。

5. 边界条件、常见坑与防漏技巧

5.1 空数组与单元素数组

很多人在刷题平台上提交失败，不是因为主逻辑错了，而是没处理边界。

height = []，返回 0。height = [3]，返回 0。这两个在双指针解法中，if n == 0的检查会拦住空数组；而在单调栈解法中，空数组不会进入循环，自然返回 0；单元素数组时栈操作也不会进入 while 循环，返回 0。但如果你用的是 DP 解法，必须先处理 n == 0，否则初始化left_max[0] = height[0]会直接下标越界。

我的习惯是：写任何解法前先想三件事——空输入、单输入、全递增、全递减、全相等。这道题里全递增如 [1,2,3,4] 答案是 0，因为水都流走了；全递减同理；全相等如 [2,2,2,2] 答案也是 0，因为没有凹槽。多跑这几个 case，基本能排除 90% 的低级错误。

5.2 累加顺序与负值过滤的陷阱

在暴力法和 DP 法里，min(leftMax, rightMax) - height[i]可能出现负数。比如 i=0 时，leftMax=height[0]，rightMax 可能小于 height[0]，相减为负。如果直接累加，答案就错了。所以要么用if water > 0过滤，要么用max(0, ...)包裹。

双指针解法不会出现负数，因为代码逻辑保证了只有height[left] < left_max时才累加，此时差值为正。但如果你把双指针的累加条件写反了，比如在height[left] >= left_max时也去累加，就会出现负数累加。我建议在写完代码后，用一个包含"两边高中间低"的用例自测：height = [3,0,0,2]，期望答案是 4（两个 0 位置各存 2 格水），如果输出不对，很快能定位问题。

5.3 从刷题到工程：这道题教给你的思维能力

接雨水这道题刷完，至少有三种思维能迁移到日常工程里。

第一种叫"状态压缩思维"。从 DP 的两数组优化到双指针的 O(1) 空间，本质上是发现了"我们不需要全量信息，只需要在正确时机维护正确信息的子集"。这在处理流式数据时很常见——比如统计一个滑动窗口的最大值，不需要保存窗口里所有元素，只需要一个单调结构就够了。

第二种叫"双端逼近思维"。两个指针从两端往中间走，适用于任何"结果由左右两侧共同决定"的问题。除了接雨水，判断回文字符串、查找有序数组中的两数之和、翻转数组，都是这个框架。

第三种叫"分层累加思维"。单调栈解法里，水是按层统计的，不是按列。这种"换个维度切分问题"的思路，在工程上就是典型的"分而治之"变体——同一个总量，按不同维度切分计算，往往能有完全不同的复杂度。

6. 面试现场模拟与延伸问题串讲

6.1 面试官追问的三个递进层次

我模拟一下这道题在面试中的完整对话流程。

第一层，你给出暴力解法。面试官点头，问"时间复杂度多少"？答 O(n²)。追问"能优化吗"？

第二层，你给出 DP 解法。面试官会问"空间能省吗"？到这里，如果你能直接写出双指针，大概率这道题就过了。但面试官可能还会问一个非常刁钻的问题：为什么双指针移动"较矮"的一侧，而不是"较高"的一侧？

答案要说到点子上：移动较矮的一侧，是因为这一侧的存水上限已经被"另一侧至少存在一根更高的柱子"锁定了，处理完它的贡献后，它就不再影响后续任何位置的积水量。如果移动较高的一侧，那根高柱子还可能成为后续位置的边界，提前移动会丢失信息。

第三层，如果你主动给出单调栈解法，面试官可能会反问"两种解法分别适合什么场景"。这时候可以根据空间需求和扩展性来展开回答，比如"数组特别大、在意空间时用双指针；如果接下来还要解决柱状图最大矩形这类同构问题时，单调栈的思路更统一"。

6.2 同源问题的对比学习路线

我建议把这几道题放在一起刷，它们共享同一套思维肌肉记忆。

第一道是"盛最多水的容器"（LeetCode 11）。它也是双指针，但是找最大面积，移动规则是"移动较短的那根柱子"，因为面积受限于短边。注意它不统计每个位置的积水量，而是整体最大面积，这是和接雨水最核心的差异。

第二道是"柱状图中最大的矩形"（LeetCode 84）。这道题是单调栈的经典应用，和接雨水正好是"镜像"关系——接雨水找凹槽积水，最大矩形找凸起扩展。两题对照着学，单调栈的弹出时机、宽度计算、边界处理就全通了。

第三道是"除自身以外数组的乘积"（LeetCode 238）。它也用到了左右两个预处理数组的思路，能帮你巩固"前缀/后缀扫描"这个基本招式。

6.3 个人实操中的最后心得与一个小技巧

最后分享一个我刷这道题时悟到的技巧，也是面试时能让你脱颖而出的点：接雨水这道题，无论哪种解法，最后的核心判断都是"每个格子的水量由较矮的边界决定"。如果你能用一句话总结这个不变量，并且在写代码时让注释或命名体现出这个不变量——比如变量名用left_wall而不是left_max，用water_level而不是h——面试官会觉得你不只是在背题，而是真正建立了解决问题的框架。

我自己实际带过的几个同学，卡住最多的反而不是双指针的边界，而是暴力法里"扫描方向"搞反：有人求 maxLeft 时从 i+1 往右扫，求 maxRight 时从 i-1 往左扫，两边都反了，debug 半小时。记住：左侧最大值要看左边所有的墙，扫描方向一定是往左；右侧最大值同理。就这么朴素。

还有一个小经验：刷这道题时，建议用纸笔至少手动跑一遍双指针的完整流程，把这个 12 个柱子的用例从头走到尾。这个过程花不了十分钟，但你对"指针移动顺序"和"何时更新最大值"的肌肉记忆会深刻很多。光看题解是学不会的，手指头过一遍才有感觉。