企业官网建设流程全解析

1. 题目到底在算什么：从暴力读题到第一版能跑的解法

在 LeetCode 热题 100 里，42. 接雨水绝对属于那种“背过题解也会卡壳”的题目。我最早在春招面试时被问到，当时能说出暴力法和动态规划，但双指针怎么推都差点意思。后来把这道题吃透，感觉整个“找峰值/凹槽”一类的问题都通透了。这篇不打算只贴答案，而是顺着从暴力到双指针的思路走一遍，同时把单调栈、备忘录等方法放在一起对比，帮你真正理解为什么双指针能优化到 O(n) 时间和 O(1) 空间。

1.1 题目还原与核心公式

题目给的是一个非负整数数组height，每个值表示一个宽度为 1 的柱子的高度。如果把这些柱子立在地上，下雨之后，凹陷处能积多少水？注意水面不能超过左右两侧柱子的高度，所以每个位置能接的水量取决于左右两侧各自最高柱子的较矮者，再减去当前柱子的高度。

用公式表达就是：

位置 i 的积水量 = max(0, min(leftMax[i], rightMax[i]) - height[i])

其中leftMax[i]是height[0..i]的最大值，rightMax[i]是height[i..n-1]的最大值。为什么是闭区间而不是开区间？因为柱子自身也算一面“墙”，如果当前位置已经是左右最高的，那它不可能积水，min(leftMax, rightMax) - height[i]正好等于 0。

举个例子，height = [0,1,0,2,1,0,1,3,2,1,2,1]，经典结果答案是 6。拿位置 2（高度 0）来看，左边最高是 1（位置 1），右边最高是 3（位置 7），较矮的是 1，所以能接1 - 0 = 1的水；位置 3（高度 2）左边最高 2，右边最高 3，较矮是 2，接水量为 0。累加所有位置，答案 6。

1.2 暴力解法：每个柱子左右扫一遍

理解了公式，第一版解法几乎是顺理成章的：对每个柱子，分别向左和向右扫描，找出两边的最大高度，然后套公式。

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

注意这里向左扫描时要从i本身开始，而不是i-1，否则会漏掉当前柱子作为左侧最高墙的情况。同样的，向右扫描也要包含i。

这个做法时间复杂度 O(n²)，空间复杂度 O(1)。数据量小的时候没问题，但 LeetCode 上height.length最多到 2×10⁴，O(n²) 就是 4×10⁸ 次操作，在 Python 里跑会明显卡顿。面试时先说出暴力解法，表明你能读懂题，但接下来必须给出更优方案。

1.3 为什么暴力能过却不该止步

暴力解法的最大问题是重复计算：每个位置的左右最大值都需要重新扫描一遍，而实际上这些最大值是可以“滚动维护”的。比如从左往右扫一遍，就能得到每个位置的leftMax；从右往左再扫一遍，又能得到rightMax。既然有了预处理数组，为什么还要每次都重新找？

这就引出了最常见的优化方向——空间换时间。而双指针则更进一步，连预处理的数组都省掉。所以接雨水这道题的精髓在于：它把“数组预处理”和“双指针收缩”两条优化路线放在同一道题里，考察的是你能不能从暴力循环里抽象出单调性。

2. 双指针为什么是正解：从备忘录到空间压缩的完整推导

很多人第一次看双指针题解时，看完代码觉得“好像懂了”，但换一道题又不会。这是因为没有理解双指针背后的推导链：暴力 → 备忘录 → 空间压缩 → 双指针。把这条链走一遍，代码自然就记住了。

2.1 动态规划（备忘录）版本先打底

先用两个数组把每个位置的左右最大值预处理出来，然后再扫一遍计算答案：

def trap_dp(height): if not height: return 0 n = len(height) 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(n): ans += min(left_max[i], right_max[i]) - height[i] return ans

这个版本时间 O(n)，空间 O(n)。面试中能写出这个已经合格，但空间还有压缩余地。观察公式，每个位置只依赖它自己的leftMax和rightMax，我们能不能不把两个数组都存下来，而是用两个变量一边扫描一边维护？

2.2 双指针的物理直觉：短板决定水位

假设我们在数组两端各放一个指针left和right，同时维护两个变量：

• left_max：从左侧到left位置遇到的最高柱子
• right_max：从右侧到right位置遇到的最高柱子

初始时left_max = height[left]，right_max = height[right]。接下来比较这两个值：如果left_max < right_max，说明左边这堵墙比右边矮，那么对于left位置来说，决定它能接多少水的一定是左边的left_max。为什么？因为右侧至少存在一堵right_max这么高的墙，而right_max > left_max，所以右边不会成为更矮的限制。于是可以直接结算：

ans += left_max - height[left]

注意这里的left_max已经包含了height[left]本身，所以结果一定非负。结算完，左指针向右移一位，同时更新left_max。反之，如果right_max <= left_max，就结算右指针位置，然后右指针左移。整个过程的物理直觉就是：水位永远被较矮的那堵墙限制，谁矮就先结算谁，结算完就向内缩一格。

2.3 严谨证明与两种等价写法

上面这种说法很多初学者会质疑：如果左边出现的最高墙有 10，右边最高墙只有 8，那left_max明明比right_max高，为什么还说“左边这堵墙矮”？这里的关键是：我们比较的不是“左右指针当前位置的墙”，而是已经扫描过的左右区域的最大高度。当left_max < right_max时，右侧的可依赖墙高度至少是right_max，它比左侧任何墙都高，所以左侧区域可以安全结算；反之亦然。

因此在代码里有两种等价实现。最常见的写法是直接比较height[left]和height[right]，同时滚动更新left_max和right_max：

def trap_double_pointer(height): if not height: return 0 left, right = 0, len(height) - 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和right_max，这个版本的逻辑更加贴近“短板决定水位”：

def trap_double_pointer_v2(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: ans += left_max - height[left] left += 1 if left < right: left_max = max(left_max, height[left]) else: ans += right_max - height[right] right -= 1 if left < right: right_max = max(right_max, height[right]) return ans

两个版本结论一致。我个人的建议是：理解第二个版本再写第一个版本，因为第二个能让你更清楚地知道“为什么要移动 left 而不是 right”。

3. 手写双指针最容易踩的四个坑

这道题代码不复杂，但我在实战里见过不少人（包括我自己）在细节上翻车。下面列出高频坑点。

3.1 坑一：更新left_max/right_max的时机

在第一种写法里，必须先更新最大值再累加，或者先累加再更新，但两种不能混。看这段错误代码：

# 错误示范 while left < right: if height[left] < height[right]: ans += left_max - height[left] # left_max 还没更新，可能为 0 left_max = max(left_max, height[left]) left += 1

第一次进入循环时left_max = 0，如果height[left] > 0，left_max - height[left]会变成负数，答案直接错了。正确顺序是：

left_max = max(left_max, height[left]) ans += left_max - height[left] left += 1

或者像第二版那样先计算再移动再更新，也能保证left_max >= height[left]，但逻辑上要绕一下，容易写错。推荐使用“先更新，后累加”的版本。

3.2 坑二：while 条件写成left <= right

如果写成while left <= right，当left和right重合时，会对同一个位置重复结算一次，导致答案偏大。比如height = [0,1,0,2]，正确结果是 1（位置 2 接水 1），但用left <= right会在最后重合位置多加一些不该加的量。记住：双指针相遇的位置本身不可能再有积水，因为那个位置左右已经被计算过，或者它自己就是边界，所以循环条件必须是left < right。

3.3 坑三：算出来的水量出现负数

出现负数的根本原因是没有理解left_max的作用。left_max表示当前位置左侧（包括当前位置）的最高高度，如果当前柱子很高，那left_max - height[left]自然为 0；但如果left_max没有及时包含当前高度，就会出现负数。不少人在一维数组里手动模拟时，看到ans += 0就放心了，结果忘了更新left_max，后面遇到凹陷位置就会算错。建议每移动一次指针，都强制自己写一遍更新逻辑。

3.4 坑四：空数组和单元素数组

LeetCode 的测试用例会有空数组，如果直接访问height[0]会越界。所以在函数开头必须先判断：

if not height: return 0

单元素数组也直接返回 0，因为一个柱子接不了水。这两种边界处理看起来简单，但在手撕代码时很容易漏掉，而面试官往往第一个就看边界条件。

3.5 完整可运行代码（Python / Java / C++ 简要）

Python 版前面已经给了，这里给一份 Java 参考：

class Solution { public int trap(int[] height) { if (height == null || height.length == 0) return 0; int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0; int ans = 0; while (left < right) { if (height[left] < height[right]) { leftMax = Math.max(leftMax, height[left]); ans += leftMax - height[left]; left++; } else { rightMax = Math.max(rightMax, height[right]); ans += rightMax - height[right]; right--; } } return ans; } }

C++ 写法几乎一样，把Math.max换成max即可。核心逻辑完全一致，不需要再单独贴。

4. 全方法横向对比：单调栈、备忘录、逐层累加、面积法

接雨水的方法远不止双指针一种。把其他主流解法放在一起对比，能帮你建立更完整的算法知识图谱。

4.1 单调栈解法：处理嵌套凹槽

单调栈的思路是：从左到右遍历柱子，维护一个从栈底到栈顶单调递减（或非递增）的栈。当遇到一根比栈顶高度更高的柱子时，说明出现了一个“坑底”，弹出栈顶作为凹槽底部，新柱子作为右墙，栈内下一根柱子作为左墙，然后计算这一层的积水量。

def trap_stack(height): stack = [] ans = 0 for i in range(len(height)): 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] ans += width * h stack.append(i) return ans

单调栈的优势在于不需要预先知道左右最大值，而是动态地在遍历过程中发现凹槽。它适合处理“嵌套结构”，比如多个连续坑洼的场景。时间复杂度同样是 O(n)，因为每个柱子最多入栈一次、出栈一次。空间复杂度 O(n)。

4.2 备忘录 vs 双指针 vs 单调栈对比表

从表里能清楚看到，双指针是时间和空间上最均衡的方案。单调栈虽然也是 O(n) 时间，但额外用了栈空间；备忘录虽然好理解，但空间开销大一倍。

4.3 其他有趣思路（逐层、几何法），以及为何不推荐

网上还能看到逐层累加法：先找出最大高度max_h，然后从高度 1 到max_h逐层扫描，统计每一层的连续空隙宽度。这个方法理解起来非常直白，但时间复杂度是 O(n × max_h)，如果柱子高度很大（比如 10000），会直接超时，面试中很少采用。

还有一种几何面积法：把柱状图看成一个整体，用“从左到右扫描不断上升的边界面积”减去柱子本身面积，再减去某些部分，推算积水量。这个方法在特定输入下很巧妙，但推导过程复杂，边界条件多，容易算错，实用性不高。我的建议是：知道有这些思路，但面试时优先讲双指针或单调栈。

4.4 面试时的推荐回答路线

如果面试官让你做这道题，我建议按这条路线回答：

1. 先复述题目，给出核心公式min(leftMax[i], rightMax[i]) - height[i]。
2. 给暴力解法，说明复杂度 O(n²)。
3. 过渡到备忘录，用两个数组优化到 O(n) 时间 O(n) 空间。
4. 最后讲双指针，说明如何用两个变量滚动维护最大值，把空间压到 O(1)。
5. 如果面试官追问“还能不能更快/更省”，再提单调栈，并说明它适合处理嵌套结构。

这个回答路线能展示你从暴力到优化的完整思维过程，而不是背了一个双指针答案。

5. 由接雨水带出的双指针通用套路与同类题迁移

双指针并不只是接雨水的专属解法，它是一大类“从两端夹逼”问题的通用武器。

5.1 什么时候该想到双指针

当你看到题目要求“在数组中找两个边界，使得某个面积/容量最大”或“计算凹槽容量”时，优先想一想能否用左右指针从两端向中间收缩。典型的判断标准有两个：

• 数组元素之间没有插入删除操作，只有扫描。
• 答案与左右边界的“较矮/较小/较窄”有关，并且移动指针后不会遗漏最优解。

接雨水里，移动较矮指针后，该位置的水量可以立即确定，不会影响后续结果，这正是双指针能成立的关键。

5.2 同类题：盛最多水的容器、柱状图最大矩形、二维接雨水

• LeetCode 11. 盛最多水的容器：同样是双指针，每次移动较矮的指针，保留较高的指针，因为面积由较矮边决定。理解接雨水的双指针后，这道题几乎是秒杀。
• LeetCode 84. 柱状图中最大的矩形：单调栈的经典应用。和接雨水相比，接雨水的单调栈是“弹出后算凹槽积水量”，最大矩形是“弹出后算矩形面积”，思路一正一反，非常适合对比学习。
• LeetCode 407. 接雨水 II：把二维问题扩展到三维，使用优先队列（堆）从外向内地分层灌水，本质上还是“短板决定水位”的思想，但数据结构和边界处理要复杂得多。

建议把这三道题放进同一个“容器/积水”专题里刷，效果比单刷一遍好得多。

5.3 我的刷题顺序建议

如果你刚开始接触这类题目，我的建议顺序是：

1. 先做盛最多水的容器，用双指针建立“移动较矮边界”的直觉。
2. 再做接雨水，先写暴力，再写备忘录，最后写双指针。
3. 然后做柱状图中最大的矩形，掌握单调栈。
4. 如果还有精力，尝试接雨水 II，感受二维扩展的难度提升。

不要一上来就背双指针代码。我见过太多同学把接雨水的代码背得滚瓜烂熟，但换一道盛最多水的容器反而不会做，就是因为没有理解“短板”这个底层直觉。

最后分享一个我自己的小技巧：现在我做接雨水，已经不再死记双指针的移动条件，而是把问题翻译成“实时维护当前左右边界之间最高的两堵墙”，然后用较矮的那堵墙结算对面的水位。如果你也曾经在双指针里绕晕，不妨先画一张柱子图，手动跑一遍 left 和 right 的移动轨迹，比看十篇题解都有效。