企业官网建设流程全解析

我先提个结论：“接雨水”这道题，是 LeetCode Hot 100 里我刷了十几遍最不亏的一道题。

倒不是说它难到天上去，而是这题把“怎么从暴力到最优”“怎么识别单调栈场景”“怎么把空间压到O(1)”这三件事全串在了一个模型里。你把这题吃透了，单调栈那类题基本等于开了一个口子；双指针那个解法更是把“由约束决定移动策略”这种思维焊死在脑子里。难怪它在 Hot 100 里排第 7，我猜出题人就是想让每一个刷题的人早点撞上它，因为后面一堆题都会用到这里的思想。

这篇文章我不打算只是贴个最优解就完事。我会把一个完整的、从一个普通刷题者视角出发的思考过程写出来：先怎么暴力想，遇到什么瓶颈，然后怎么优化成动态规划，再发现单调栈更本质，最后才发现双指针才是最优雅的那个。每个解法我都给出完整可跑通的代码（C++ 和 Python 双版本）、复杂度分析、边界条件，还有我实际提交时踩过的坑和心得。

1. 题目理解与核心解题思路

1.1 题目到底在问什么

给你一个非负整数数组height，每个元素代表一个宽度为 1 的柱子的高度。把这些柱子画在二维平面里，问下过雨后能接多少单位的雨水。

这个描述看着简单，但真动手时容易在几个点上含糊。我拆开说：

• 柱子是实心的，宽度固定为 1，单位体积的雨水就是“一格”。
• 雨水是自己找平的，它不会悬空，必须存在一个“低洼处”，且左右两侧都有能挡住它的更高柱子。
• 边界上的柱子装不了水，哪怕它外侧是无底洞，水也会直接流出去。
• 数组元素是非负整数，0 也是合法的，0 表示那个位置没有柱子。

“能接多少雨水”这句话背后的计算单位是：每个柱子的列上方的空间能存几格水，把这些格数全部加起来。

拿一个经典例子来说：

height = [0,1,0,2,1,0,1,3,2,1,2,1]

这个例子的答案是 6，你手算也能验证：索引 2 上方存 1 格，索引 4、5、6 这几个位置分别存 1、2、1 格，索引 9、10 分别存 1、1 格，加起来正好 6。

1.2 接水的本质：两个方向的约束

为什么这题不是简单的“找坑”？因为一个位置到底能不能存水、存多少水，取决于它左边最高柱子和右边最高柱子之间的“短板”。

一个位置i能存的水量写成公式就是：

water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])

其中：

• leftMax[i]表示索引i左边（含自身）柱子的最高高度；
• rightMax[i]表示索引i右边（含自身）柱子的最高高度；
• 取两者较小值，再用这个较小值减去当前位置柱子的高度；
• 如果结果是正的，说明这个位置能存水；如果是负数或 0，说明存不了。

注意：左边或右边没有柱子（即当前是边界的情况），leftMax或rightMax就等于自身高度，那min - height[i] = 0，天然存不了水。

这个公式是整个题目的灵魂。后面所有解法，本质上都是在“怎么更快地算出每个位置的 leftMax 和 rightMax”这件事上做文章。

1.3 为什么建议先把暴力解想清楚

很多人一上来就背最优解，但真到了面试或者写题的时候，一旦题目变形就抓瞎。我自己的经验是：先想暴力，再逐步优化，这个过程中的每一步都是值的。

暴力法就是按公式直接来：对于每个位置i，分别向左、向右扫描一遍找最大值，然后套公式计算。时间复杂度 O(n^2)，空间 O(1)。这段代码写出来非常简单，但它最大的价值不是性能，而是帮我们确认“答案的公式”是对的。当你后面用复杂解法写出结果时，可以用暴力解的结果来交叉验证。

我在本地写题时，就经常把暴力解作为“对照版本”，其他解法跑完先跟它比对输出，确保没改错逻辑。

2. 解法一：动态规划（前后缀最值）

2.1 思路演进：把重复扫描变成预计算

暴力解法慢在哪儿？每个位置都要向左右各扫描一遍，中间大量重复比较。那自然想到：我能不能提前把每个位置的左边最大值和右边最大值都算出来，存到数组里，之后直接用？

这不就是动态规划里最经典的前缀/后缀数组技巧嘛。我们分别从左往右、从右往左各扫一遍，就把leftMax和rightMax两个数组填满了，然后再用公式累加一趟得出答案。

• 时间复杂度：O(n)，扫了三趟，每趟线性；
• 空间复杂度：O(n)，两个辅助数组。

2.2 完整代码

C++ 版本：

class Solution { public: int trap(vector<int>& height) { int n = height.size(); if (n <= 2) return 0; // 少于3根柱子不可能存水 vector<int> leftMax(n), rightMax(n); leftMax[0] = height[0]; for (int i = 1; i < n; ++i) { leftMax[i] = max(leftMax[i - 1], height[i]); } rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; --i) { rightMax[i] = max(rightMax[i + 1], height[i]); } int ans = 0; for (int i = 1; i < n - 1; ++i) { ans += max(0, min(leftMax[i], rightMax[i]) - height[i]); } return ans; } };

Python 版本：

class Solution: def trap(self, height: List[int]) -> int: n = len(height) if n <= 2: 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]) ans = 0 for i in range(1, n - 1): ans += max(0, min(left_max[i], right_max[i]) - height[i]) return ans

2.3 几个容易栽的细节

n 小于等于 2 直接返回 0。这个我一开始老是忽略。想想看，0 根柱子不可能装水，1 根、2 根也一样，水放上去直接流走了，所以少于 3 根柱子直接返回 0 是安全的。加了这行，不仅省了循环，还避免了下标越界的问题。

leftMax[i] 包含 height[i] 自身。这里有个概念上的细节：我们找的是“左边最高”，这个“左边”到底包不包含自己？包含。为什么？因为公式min(leftMax, rightMax) - height[i]里，如果左边界挡板就是自己（比如i正好是整个数组的最高点，那 leftMax[i] = height[i] ），减出来是 0，逻辑通顺。如果不包含自身，那对于边界位置和下降沿就会出错。

边界位置（i=0 和 i=n-1）不需要计算。我们的累加循环是从1到n - 2，因为最左边和最右边的柱子外侧没有墙壁，水存不住，公式必然输出 0，所以干脆不参与循环。

2.4 动态规划解法怎么看才算真会了

我的判断标准：你闭上眼能画出 leftMax 和 rightMax 数组在样例上的变化过程，并且能解释为什么第一趟从左往右扫、第二趟从右往左扫，而不是反过来。这两趟的顺序不是随意的：leftMax 依赖左边的结果，所以必须从左往右；rightMax 依赖右边的结果，所以必须从右往左。

如果你想挑战一下，可以想想二维版本的接雨水怎么解——那个是一个 hard 题（LeetCode 407），它核心思想其实和这个一维版本一脉相承，但用了优先队列。这也能反过来说明一维版本的前缀最值思想有多重要。

3. 解法二：单调栈（更本质的理解）

3.1 为什么还要学单调栈

动态规划解法已经 O(n) 了，很多人觉得没必要再学。但我想说，单调栈解法在思维层面是另一套东西：它不是“每个柱子存多少水”的列视角，而是“每一层水是怎么被左右边界夹出来”的行视角。

而且，单调栈是面试高频考点，你不在这道题里学会，后面接“柱状图中最大的矩形”（LeetCode 84）、“每日温度”（LeetCode 739）、“滑动窗口最大值”里的单调队列思想，会更痛苦。接雨水恰恰是最适合入门单调栈的题目之一。

3.2 单调栈的核心逻辑

维护一个单调递减栈（栈底到栈顶是递减的，也就是栈顶是最小的），栈里存的是柱子的下标，不是高度。为什么存下标？因为后面计算宽度时需要下标差。

遍历每个柱子时：

1. 如果当前柱子高度小于等于栈顶柱子的高度，入栈（栈依然满足递减性质）；
2. 如果当前柱子高度大于栈顶柱子的高度，说明栈顶这个柱子形成了一个凹槽的底部，它左边的柱子（栈里下一个元素）和当前柱子是它的左右墙壁，这时就可以结算积水了。

核心计算逻辑：

h = min(height[left], height[right]) - height[bottom] // 水层高度 w = right - left - 1 // 水层宽度 ans += h * w

注意这里算的是一个水平层的水量，不是一整列。这一点非常容易混淆。

3.3 完整代码

C++ 版本：

class Solution { public: int trap(vector<int>& height) { int n = height.size(); if (n <= 2) return 0; int ans = 0; stack<int> st; for (int i = 0; i < n; ++i) { while (!st.empty() && height[i] > height[st.top()]) { int bottom = st.top(); st.pop(); if (st.empty()) break; // 左边没有墙，存不了水 int left = st.top(); int w = i - left - 1; int h = min(height[left], height[i]) - height[bottom]; ans += w * h; } st.push(i); } return ans; } };

Python 版本：

class Solution: def trap(self, height: List[int]) -> int: n = len(height) if n <= 2: return 0 ans = 0 stack = [] for i in range(n): while stack and height[i] > height[stack[-1]]: bottom = stack.pop() if not stack: break left = stack[-1] w = i - left - 1 h = min(height[left], height[i]) - height[bottom] ans += w * h stack.append(i) return ans

3.4 单调栈的细节和坑（这里全是实战心得）

坑一：pop 之后要判断栈是否为空。这个是初学者最容易漏的。当bottom出栈后，如果栈空，说明bottom左边没有任何更高的柱子，那么水会从左边界直接流走，根本存不起来，所以必须break跳出循环，而且不能把这个位置入栈（或者其实还是要入栈，因为当前柱子会成为新的左边界备选）。这里的st.push(i)是在 while 循环之外，会照常执行。

坑二：栈里存的是下标，比存高度好用。如果只存高度，计算宽度时没法确定两个柱子之间隔了多少个单位。所以不管是计算宽度i - left - 1，还是判断左墙st.top()，都是基于下标的。

坑三：横向算面积，不是纵向。很多人第一次写单调栈解法，会写在 while 循环里一层一层地加，以为是一次把一列的水都算完。实际上单调栈是遇到一个凸起就结算一层水。你可以把最终结果想象成“横着切出很多层水”，每一层都由一个局部的“左墙-坑底-右墙”三元组构成。

坑四：等于号的处理。当前柱子高度等于栈顶时，应该入栈还是不入栈？两种做法其实都能得出正确答案，但入栈的代码更简洁、更通用。你可以试着想想：如果高度相等，pop 掉再结算一点水，和直接入栈，最终总和一样吗？答案是：一样。因为等高的两个柱子之间没有凹槽，不会产生水。但直接入栈能避免不必要的计算，所以代码里用的是>，不是>=。

3.5 单调栈状态模拟

我手动模拟一遍，看状态变化，这样比看代码更直观。

假设height = [0,1,0,2,1,0,1,3,2,1,2,1]：

• i=0：栈空，push(0)，栈：[0]
• i=1：height[1]=1 > height[0]=0，pop(0)，栈空，break；push(1)，栈：[1]
• i=2：height[2]=0 <= height[1]=1，push(2)，栈：[1,2]
• i=3：height[3]=2 > height[2]=0，pop(2)，栈顶是1，left=1，w=1，h=min(1,2)-0=1，ans+=1；继续 height[3]=2 > height[1]=1，pop(1)，栈空，break；push(3)，栈：[3]
• i=4、5、6……后面读者可以自行推演。

每次结算时的三元组(left, bottom, right)就是一层水。你模拟完之后会发现一个很神奇的事：一个柱子可能参与多次结算，但每次角色不一样。比如柱子 1 高度是 1，它既作为 i=2 的左墙，又作为 i=2 的坑底被 pop 掉过。这就是单调栈的魅力：元素不是用一次就没了，而是在不同阶段扮演不同角色。

4. 解法三：双指针（最优解）

4.1 本质：用两个方向逼近，替代预处理数组

动态规划解法用了 O(n) 空间存前后缀最大值，能不能把空间省掉？

答案是：可以，而且算法更简洁。核心思想是：我们不需要把每个位置的 leftMax 和 rightMax 都算好，只需要知道当前位置的“短板”是谁。

如果当前我们已经知道“左侧最大值”比“右侧最大值”小，那么对于左侧这个位置来说，它的储水量就由左侧最大值决定（因为右侧最大值一定大于它）。于是我们不用关心右边具体怎么分布，直接结算这个位置的储水量，然后移动左指针。

反之，如果右侧最大值比左侧最大值小，就结算右侧位置的储水量，移动右指针。

这个“短板决定结算哪一侧”的思路，其实做了一次非常漂亮的剪枝：用两个游标代替两个数组。

4.2 代码实现

C++ 版本：

class Solution { public: int trap(vector<int>& height) { int n = height.size(); if (n <= 2) return 0; int left = 0, right = n - 1; int leftMax = 0, rightMax = 0; int ans = 0; while (left < right) { leftMax = max(leftMax, height[left]); rightMax = max(rightMax, height[right]); if (leftMax < rightMax) { ans += leftMax - height[left]; ++left; } else { ans += rightMax - height[right]; --right; } } return ans; } };

Python 版本：

class Solution: def trap(self, height: List[int]) -> int: n = len(height) if n <= 2: return 0 left, right = 0, n - 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 left_max < right_max: ans += left_max - height[left] left += 1 else: ans += right_max - height[right] right -= 1 return ans

4.3 为什么双指针是对的——从公式角度硬解释

这题的双指针，我前面讲的思路还只是直觉。你如果想要严谨一点的证明，可以这样想：

对于任意一个位置i：

• 如果它在left这一侧被处理，说明此刻leftMax < rightMax。
• 因为rightMax已经是右侧区间[left+1, ...]或者更准确地说，是[left, right]中从right往左扫到的最大值，而真正的rightMax[i]（即位置 i 右侧所有柱子的最大值）一定大于等于当前的rightMax，所以rightMax[i] >= rightMax > leftMax。
• 于是min(leftMax[i], rightMax[i]) = leftMax[i] = leftMax。
• 所以ans += leftMax - height[left]是准确无误的。

反过来，如果leftMax >= rightMax，处理右指针时同理，min(leftMax[i], rightMax[i]) = rightMax。

这个证明的意义在于：双指针不是“碰巧对了”，而是每一步都精确地复现了动态规划公式里的 min 操作。我们只是把“预计算整个数组”变成了“边走边决定每侧谁说了算”。

4.4 双指针解法的几个易错点

易错点一：更新 max 要先于计算水量。leftMax = max(leftMax, height[left])必须在计算ans += leftMax - height[left]之前完成。不然当前柱子可能就是新的最大值，你不更新的话，计算出来的水量可能是负数。

易错点二：等于号归哪边。代码里用的是if (leftMax < rightMax)，也就是两者相等时走 else 分支，处理右指针。其实走哪边结果都一样。你可以试着把条件改成<=，最后答案不会变。因为相等时，无论结算左边还是右边，都是max - height[i]，高的一侧能保证另一侧不缺水，结算一侧时另一侧仍然可以作为“靠山”。

易错点三：while 循环条件left < right而不是<=。这个其实想明白就简单：当left == right时，两个指针指向同一个位置，这个位置已经不需要再计算了，因为它的两边都扫过了。但如果你不小心写成<=，会导致 left 和 right 同时指向同一个索引，然后leftMax和rightMax都包含这一个位置，计算出来max - height[i] = 0，不会影响答案，但属于多余的判断。只是left会移动过头，可能越界。所以写成<是安全且优雅的。

4.5 双指针的复杂度

• 时间复杂度：O(n)，一次线性扫描；
• 空间复杂度：O(1)，只用了几个临时变量。

这是这道题的最优解，也是我在面试中最推荐的写法。原因不只是省空间，而是它把“动规 + 空间压缩”这件事用一个简单清晰的框架表达了出来，现场写不容易错。

5. 常见问题与实战经验

5.1 刷了几百遍才总结出的避坑清单

我把这题所有解法中容易出问题的地方整理成一张表，方便随时查阅：

5.2 从这题延伸出来的几个变体

变体一：柱状图中最大的矩形（LeetCode 84）。这题正好是“接雨水”的镜像问题。接雨水是找“坑”能装多少水，它用单调递增栈；而 LeetCode 84 是找“最大矩形面积”，用的是单调递减栈。这两题对照着刷，是理解单调栈的最佳组合。

变体二：二维接雨水（LeetCode 407）。从一维变二维，柱子变成了地形网格，需要从边界向内做 BFS + 优先队列。虽然难度上了个台阶，但核心仍然是“边界最矮的墙决定能存多少水”，可以说是一维接雨水的思想拓展。

变体三：每日温度（LeetCode 739）。这题用单调栈来求“下一个更大元素的距离”，跟接雨水的单调栈思想是同一个套路：利用栈维护一个单调序列，在弹出时结算信息。

变体四：接雨水 II（和二维的区别）。三维空间里接水，更接近于“多个水箱拼在一起”的思路，一般不会出现在面试里，但竞赛和 hard 题里见过。

5.3 面试环节怎么编排这道题

如果你在面试中被问“接雨水”，我建议回答顺序不是直接丢最优解，而是这样组织，体现你的思维过程：

1. 先说暴力解：每个位置找左右最大值，O(n^2)。先确认题意和边界。
2. 再优化：能不能预计算 leftMax/rightMax？可以，O(n) 时间 O(n) 空间。把动态规划版本写出来。
3. 然后提空间优化：可以不用两个数组，用双指针，边走边比较左右最大值，O(1) 空间。把双指针写出来。
4. 最后可以补充一句：还有一个单调栈解法，换个视角按层结算，也能做到 O(n) 时间 O(n) 空间，如果需要我可以展示。

这套顺序的好处是：展示了你从暴力到最优的完整思维链条。面试官通常不会拦着你，反而会觉得你的思路很清晰。如果一开始就直接甩双指针，虽然对，但容易显得像背题。

我自己的经验是，面试官最喜欢追问的点是：“你为什么在leftMax < rightMax时移动左指针？”这个问题只要你能用前面 4.3 那个 min 公式的角度去解释，基本就稳过。

5.4 我在本地测试时常用的几组用例

除了 LeetCode 自带的样例，我还会用下面这些用例做交叉验证：

• [0,0,0,0,0]：全零，结果 0；
• [1,0,1]：单个凹槽，结果 1；
• [1,0,2,0,3]：嵌套凹槽，结果 1 + 2 = 3（索引 1 存 1，索引 3 存 2）；
• [4,2,0,3,2,5]：经典混合场景，结果 9；
• [5,4,3,2,1]：单调递减，结果 0；
• [1,2,3,4,5]：单调递增，结果 0；
• [3,0,0,0,3]：一个大坑中间全空，结果 9。

每组用例我都会用暴力解、动态规划、单调栈、双指针四种方法分别跑一遍，确保输出一致。这个方法帮我抓出过很多隐藏 bug，比如单调栈版本在[4,2,0,3,2,5]这种多层嵌套场景中最容易算错。

5.5 踩坑实录：我写单调栈当天差点放弃

我第一次写单调栈版本的时候，被“到底什么时候结算”绕晕了。我一度以为单调栈解法是“每个凹槽结算一次”，结果代码里一行if (st.empty()) break;漏掉了，提交后有个用例挂了，我以为栈的维护方式错了，查了半天。

后来我反反复复模拟了几个用例才明白：当bottom被弹出去后，如果栈空，说明它左边没有柱子了，水直接流走，不产生积水。这行代码不是优化，是正确性的必要条件。

还有一次，我在双指针解法上纠结了很久：为什么leftMax < rightMax时只能结算左边？右边不是还没结算吗？后来想通了：当前位置的水量只取决于左右最大值中的较小值，既然右边最大值已经大于左边最大值了，那右边具体是什么根本不重要，因为“短板”已经确定了。这个思路一旦理解，双指针解法你再也不会忘。

5.6 个人总结：这题练的是什么能力

“接雨水”表面上是一道算法题，但它练的是三个层次的思维：

第一层，建模能力：把“下雨积水”这种生活场景抽象成数学公式，找到每个位置的储水量等于左右最大值的较小值减自身高度。

第二层，优化意识：同样的公式，怎么从 O(n^2) 优化到 O(n)，再从 O(n) 空间优化到 O(1) 空间。这个过程比答案本身更有价值。

第三层，工具迁移：单调栈不止能解决接雨水，还能解决一堆看似不相关的问题。你在这题里打下的基础，会在后面遇到“下一个更大元素”“最大矩形”“滑动窗口”等问题时突然派上用场。

如果你现在正在刷题，而且刷到 Hot 100 前几题，我建议你在接雨水这里多停留一会儿，把上面四种解法都亲手写一遍，模拟几组用例。等你写出双指针并证明它的正确性时，你会明显感觉到自己的思维水平上了一个台阶。