企业官网建设流程全解析

在算法面试里，"单调栈"这仨字一出来，很多人的第一反应是"听过，但不知道什么时候用"。而 LeetCode 第 42 题"接雨水"（Trapping Rain Water）恰恰是把它推到台前的最佳载体。这题表面看是个数组题，刷多了你会发现它其实在考一个很本质的东西：你能不能跳出"逐个格子算"的惯性，转而去捕捉"坑"的结构——而单调栈，就是为这种结构而生的工具。

这篇文章我不打算只是贴个能过的代码。我会把单调栈解法里最容易让人懵的地方——为什么栈底到栈顶是递减的、为什么出栈时才算"接到水"、宽度为什么是i - stack[-1] - 1——全部拆开讲透，再附上完整的可运行代码和踩坑总结。无论你是面试前突击，还是单纯想弄懂这题，这篇都值得花十分钟读完。

1. 接雨水的直觉陷阱：为什么暴力解会把复杂度打上天

1.1 题目的真实场景

先明确问题本身。给定n个非负整数，每个数代表宽度为 1 的一根柱子的高度。下雨之后，这些柱子之间能存住多少水？LeetCode 给的标准示例是[0,1,0,2,1,0,1,3,2,1,2,1]，答案 6。

看到这种问题，人脑第一反应其实是"看凹槽"：哪里低、两边哪里高，中间就能兜住水。但把这个直觉翻译成代码，绝大多数人会直接掉进第一个坑——按柱子逐个扫，对每个柱子向左右分别找最高墙。说起来很顺：某个位置能存的水，等于min(左侧最高, 右侧最高) - 当前高度，如果结果是正数就累加。

def trap_brutal(height): n = len(height) ans = 0 for i in range(n): left_max = max(height[:i+1]) # 实际应写循环取左侧最高 right_max = max(height[i:]) # 实际应写循环取右侧最高 ans += max(0, min(left_max, right_max) - height[i]) return ans

这个解法好不好？答案是对的，但每个位置都做一次全范围扫描，时间复杂度是 O(n²)。LeetCode 上这题的n上限是2 * 10^4，O(n²) 就是 4 亿次操作，Python 跑起来会明显卡顿，勉强能过测试但没有任何面试亮点。更关键的是，这个解法暴露了一个思维盲区：它把每个位置孤立地当成一个格子，而忽略了柱子之间的前后依赖关系。

1.2 水能存多少，取决于"墙"而非"格子"

我见过很多人卡在接雨水这道题上，本质上不是不会写代码，而是没想明白一个物理事实：一个位置能不能积水，不取决于它自己有多矮，而取决于它左右两边是否真的有墙把它围住。而且这两堵墙之间，往往隔着好几个柱子。

拿[2, 1, 0, 1, 3]来说，中间三个位置都能存水，但存水的"左墙"其实是下标 0 的 2，"右墙"是下标 4 的 3。中间下标 1、2、3 连成一片，共同构成了一个大的凹陷区域。如果你按单个格子算，会发现下标 2（高度 0）的左右墙分别是 1 和 1，只能存 1 格水——这没错，但下标 1（高度 1）同样是左右墙 1 和 1，存 0 格。这三个格子各自算出来的结果加在一起，恰好等于整个凹陷能接的总水量 3。

这个例子的启发是：接雨水本质上是一个"区域"问题，不是一个"点"问题。想高效求解，你就需要一种能"记住之前见过谁、并且回头清算"的数据结构。这正是栈出场的地方——它能让你从左到右扫一遍，遇到右墙时，回头把之前攒着的"坑底"一个个弹出来结算。

2. 为什么单调栈能天然匹配"找坑"这件事

2.1 从"单调"到"低谷"：一个反直觉的视角转换

"单调栈"听起来很高深，拆开就两句话：栈内元素按某种顺序排列，要么从栈底到栈顶递增（单调递增栈），要么递减（单调递减栈）。关键是什么时候用递增、什么时候用递减，这取决于你想找的是"下一个更大元素"还是"下一个更小元素"。

接雨水用的单调栈，我试过不少写法，最顺的是维护一个高度单调递减的栈。什么意思？从左往右遍历柱子时，只要当前柱子比栈顶柱子矮，就把它压进去——栈里的高度就保持从底到顶递减。一旦遇到比栈顶高的柱子，栈顶那个"矮柱"就成了一个坑底，而当前这根高柱就是坑的右墙，栈里紧挨着坑底的那根柱子就是左墙。

你可以把单调栈想象成"在连绵起伏的山里，边走边记录一路下坡时经过的洼地"。只有在下坡结束、开始上坡时，你才真正看到刚才那个洼地的深度。同理，只有新柱子比栈顶高时，之前的"洼地"形状才算完整，可以结算水量。

这就是单调栈解决接雨水的核心视角转换：站在"填坑"的角度看，而不是站在"数水"的角度看。你不需要知道全局最高墙在哪，你只需要知道"当前这堵右墙"和"刚刚弹出的坑底"以及"坑底左边最近的墙"之间，能不能形成一个局部蓄水区。

2.2 栈里存什么？下标，不是高度

初学者最容易犯的错，是在栈里存高度值。一定存下标。原因有三个：

1. 算宽度需要左右墙的位置差：右墙下标减去左墙下标再减 1，就是你这次能接水的水平宽度。只有下标才能做减法，存高度算不出宽度。
2. 算高度需要找栈中下一个元素：坑底弹出后，新的栈顶就是左墙，你要拿它去和右墙高度取最小值。这个"弹出后看新栈顶"的操作，天然依赖栈里存的是带顺序的下标。
3. 高度相等的情况需要靠下标区分：两个同为 2 的柱子，虽然高度一样，但它们围出的宽度区域可能跨了多个柱子，没法用高度值表达。

栈底永远是当前扫描过的、尚未被"更高的右墙"触发结算的柱子。栈顶则永远是目前扫描范围内右边最低的柱子——因为一旦有比它矮的，矮的会压在它上面；一旦有比它高的，它就被弹出去结算了。

3. 单调栈解接雨水的完整实现，逐行拆给它看

3.1 代码先跑起来

话不多说，直接上能 AC 的标准写法。我用 Python 写，因为结构最清楚，思路看懂后翻译成 Java 或 C++ 都很容易。

def trap(height): """ 用单调递减栈求接雨水量 时间复杂度 O(n)，空间复杂度 O(n) """ if not height: return 0 n = len(height) stack = [] # 单调递减栈，存柱子下标 ans = 0 for i in range(n): # 当前柱子比栈顶高，说明形成了"坑"，准备结算 while stack and height[i] > height[stack[-1]]: top = stack.pop() # 弹出的是坑底（当前最低点） if not stack: # 左边没有墙，形不成存水区 break left = stack[-1] # 新栈顶 = 左墙下标 width = i - left - 1 # 水平宽度：左右墙之间隔了多少个柱子 h = min(height[left], height[i]) - height[top] # 能积水的有效高度 ans += width * h stack.append(i) # 当前柱子入栈，等待未来被结算 return ans

把示例[0,1,0,2,1,0,1,3,2,1,2,1]跑一遍，输出 6，通过。但跑通只是最低要求，下面我会把每行代码背后的物理意义讲清楚。

3.2 while 循环触发的是"结算时刻"

很多人看不懂这段代码，关键在于不理解while循环在干什么。它在做的不是"边扫边存水"，而是等到右墙出现的那一刻，回头一次性结算掉之前所有能存水的位置。

比如遍历到下标 3（高度 2）时，栈里的下标是[0, 1, 2]，对应高度是[0, 1, 0]。此时height[3] = 2，比栈顶的高度 0 大，于是触发 while：

• 弹出栈顶下标 2（高度 0），这是坑底。
• 新栈顶是下标 1（高度 1），这是左墙。
• 右墙是当前下标 3（高度 2）。
• 宽度 =3 - 1 - 1 = 1（就是下标 2 这一个柱子）。
• 高度 =min(1, 2) - 0 = 1。
• 面积 =1 * 1 = 1，累加。

这就是下标 2 那个凹槽接的 1 格水。注意这里结算完之后，栈变为[0, 1]。接着循环继续判断height[3] = 2 > height[1] = 1，再次触发结算：

• 弹出栈顶下标 1（高度 1），这是新的坑底。
• 新栈顶是下标 0（高度 0），这是左墙。
• 右墙仍是当前下标 3，高度 2。
• 宽度 =3 - 0 - 1 = 2（横跨下标 1 和 2 两个位置）。
• 高度 =min(0, 2) - 1 = -1？等等，负的？

这里就出现了一个必须处理的细节——min(0, 2) = 0，减去坑底高度 1 后是负数，说明这个"坑"的左墙根本不够高，攒不住水。而我们的代码里没有显式判断正负，为什么还能得到正确答案？

3.3 负数高度的真实含义与代码的隐形保护

回到刚才的情况，min(0, 2) - 1 = -1，宽度 2，乘积是 -2，累加进去不就错了吗？不会，因为注意 while 循环里有一行提前 break：

if not stack: break

在弹出下标 1 之后，栈还剩一个下标 0。此时我们没有 break，继续走。但min(0, 2) - 1 = -1是负的，按理说该出问题…… 实际上，细看发现这里我的示例不够严谨。让我给一个更干净的触发场景：[3, 2, 1, 2]。

• 下标 0（3）入栈，栈 [0]
• 下标 1（2）入栈，栈 [0, 1]
• 下标 2（1）入栈，栈 [0, 1, 2]
• 下标 3（2）触发 while：
  • 弹出栈顶 2（高 1），栈 [0, 1]，left = 1（高 2），width = 3-1-1 = 1，h = min(2,2) - 1 = 1，ans += 1。
  • 继续判断，height[3] = 2 > height[1] = 2？不是大于，是等于，while 停止。
  • 下标 3 入栈，栈 [0, 1, 3]。

这个过程完全没问题，结算的都是正的。刚才[2,1,0,1,3]里的"负数"情况我在哪一步弄混了？让我重新理一遍：

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

• 下标 0（2）入栈，栈 [0]
• 下标 1（1）入栈，栈 [0, 1]
• 下标 2（0）入栈，栈 [0, 1, 2]
• 下标 3（1）触发 while：
  • 弹出栈顶 2（高 0），栈 [0, 1]，left = 1（高 1），width = 3-1-1 = 1，h = min(1,1) - 0 = 1，ans += 1。
  • 继续判断，height[3] = 1 > height[1] = 1？等于，while 停止。
  • 下标 3 入栈，栈 [0, 1, 3]。
• 下标 4（3）触发 while：
  • 弹出 3（高 1），栈 [0, 1]，left = 1（高 1），width = 4-1-1 = 2，h = min(1,3) - 1 = 0，ans += 0。
  • 继续判断，height[4] = 3 > height[1] = 1？是，弹出 1（高 1），栈 [0]，left = 0（高 2），width = 4-0-1 = 3，h = min(2,3) - 1 = 1，ans += 3。
  • 总 ans = 1 + 3 = 4。

这个例子里根本没有负数。我刚才说的负数情况其实不会出现，是因为 while 循环的触发条件是height[i] > height[stack[-1]]，也就是右墙一定比坑底高；而左墙高度是height[stack[-1]]（新栈顶），它可能是 0，此时min(左墙,右墙)可能小于坑底高度，结果确实可能是负的。比如栈里是[0, 1]，height 是[0, 1]，当前高度 5，弹出 1 后左墙是 0，min(0, 5) - 1 = -1。

那代码为什么没错？因为这种情况要积累到足够宽才会出现，而实际上仔细算，负的结果乘以正宽度，会污染答案。但 LeetCode 的测试用例里[0,1,1,5]这种形状不存水，所以有些实现里不加正负判断也能过——这其实是隐患。稳妥的写法是：

water = min(height[left], height[i]) - height[top] if water > 0: ans += width * water

加一个正数判断，逻辑无懈可击。很多题解里省略这一步，不是因为它是对的，而是因为恰好没碰上把次数算成负数的用例。我会建议你在自己的代码里加上，面试时主动提这个细节，考官印象会好很多。

4. 和暴力、双指针、动态规划放在一张桌上对比

4.1 三种主流思路的复杂度与适用边界

接雨水这道题的经典解法不止单调栈一种。为了让你面试时不慌，我把主流的四条路都摆出来对比一下。

暴力解法是我们开头见过的，不多说。动态规划解法的思路是：从左往右扫一遍，记录每个位置左边的最高墙left_max[i]；再从右往左扫一遍，记录右边的最高墙right_max[i]；最后每个位置能存的水就是min(left_max[i], right_max[i]) - height[i]的正数部分。这个解法本质上是"空间换时间"，把重复的扫描结果缓存下来。它和单调栈的区别在于：动态规划是"每个位置单独算"，单调栈是"按整个坑统一算"。两者最后答案一样，但思考模型完全不同。

双指针解法是我个人最喜欢在面试时先讲的方案，因为空间 O(1) 且思路很优雅：左右两个指针往中间走，维护left_max和right_max，哪边的最高墙更矮，就结算哪边当前指针的积水量，然后把指针向中间挪一步。因为最终水量由矮的那边决定，所以矮的那边可以直接算，不需要等另一边。

4.2 单调栈独有的优势：不只是为这一题准备的

既然双指针空间更省，为什么还要学单调栈？因为单调栈是一个通用工具，接雨水只是它的一个应用场景。一旦你掌握了"单调栈触发结算"的思维模型，后面遇到这些题会非常顺：

• LeetCode 84. 柱状图中最大的矩形：同样是单调栈，但维护的是递增栈，遇到矮柱子时弹出结算矩形面积，宽度计算逻辑和接雨水几乎一摸一样。
• LeetCode 739. 每日温度：单调递减栈，找到下一个更高温度的位置，入栈出栈的时机和接雨水的"触发结算"高度相似。
• LeetCode 496. 下一个更大元素：经典单调栈入门题，搞清楚这个再看接雨水，会轻松很多。
• LeetCode 316. 去除重复字母（困难）：单调栈加额外条件，保障字典序最小。

所以我的学习路径建议是：先做 496 和 739 熟悉单调栈的入栈出栈，再做 42 理解"按坑结算"，最后挑战 84 和 316。这个顺序下来，你对单调栈的掌握会远比背一道题扎实。

4.3 什么时候别用单调栈：警惕"思维定式"

不过我也得泼一盆冷水：接雨水不是非单调栈不可，甚至单独看这题，双指针是更优解。如果面试时你只会单调栈，一旦面试官追问"能不能把空间优化到 O(1)"，你就被动。所以仅仅会一种解法是不够的。

我的建议是：面试答这题时，先把暴力思路一句话带过表明你懂问题本质，然后给出双指针或单调栈，最后主动提一句"这题还能用单调栈做，核心是按坑结算"。这样既展示广度，又展示深度。实际工作中，刷题不是为了炫技，而是为了锻炼"把问题抽象成已知模型"的能力。单调栈的抽象模型就是"找下一个更大/更小的转折点"，这个模型很值钱，值得你花时间彻底吃透。

5. 单调栈写法的边界细节与调试心得

5.1 栈空、等高、负数水量，三个最容易翻车的地方

写单调栈解接雨水，90% 的 bug 出在这三处。我一个个说，这些全是血泪经验。

第一，栈空必须先判断。弹出坑底后，如果栈空了，说明左边没有墙，直接 break 或 continue，不参与结算。比如[3, 2, 1]这种只在下降的数组，一个水都存不了，但如果你不处理栈空，代码会在stack[-1]处抛 IndexError。

第二，等高的柱子别乱弹。while 循环的触发条件是height[i] > height[stack[-1]]，用的是严格大于，不是大于等于。为什么不能大于等于？以[2, 2, 1, 2]为例。如果使用>=，在下标 1（高度 2）时就会把下标 0 弹出，此时栈空，什么也算不了；而用严格>，两个同为 2 的柱子会都留在栈里，后续遇到更高的右墙时，它们能作为连续的左墙参考，宽度计算更准确。等高的墙体虽然高度相同，但它们分别标记了不同的水平位置，不能因为高度相等就合并。很多题的坑都出在这里。

第三，结算的宽度用"左右墙下标差减 1"。别直接用i - top，那样会把坑底自己占的那一格宽度错误记成 1，而实际上下标top已经弹出，当前下标i和左墙stack[-1]之间隔了多少个旧柱子，才是真正的蓄水宽度。比如[3, 1, 2]，计算下标 1 的坑时，左右墙下标是 0 和 2，宽度应该是 1，i - top却等于 2，完全错误。这是个非常隐蔽的细节，我见过好几个刷题群里的老手都在这翻车。

为了更好理解，我给 5.3 小节附一个完整的调试示例。

5.2 可视化调试法：用"栈状态表"代替干瞪眼

如果你还是没完全转过来，我教你一个笨但极有效的方法：把每次循环后的栈、当前下标、累计答案画成一张表。拿[4, 2, 0, 3, 2, 5]为例，手动走一遍：

最终答案 9，和手动算的完全一致。你可以在电脑上跑一遍这个表，再对照代码看每一步，单调栈的图像感会瞬间清晰起来。我在学习时发现，光看代码永远隔层纱，手动模拟三个用例之后，"触发结算"的时机就刻进脑子了。

5.3 一道五分钟自测题

检验你有没有真懂，试着自己推一遍[1, 0, 2, 1, 3, 1, 2]的完整出栈入栈过程，看能不能得到答案 4。思路提示：重点观察下标 1 被弹出时的左墙是谁、宽度是多少；下标 5 和 6 之间的小坑会不会触发结算。推完再去 LeetCode 验证，如果一次就对了，恭喜，你以后遇到任何单调栈题都有底气了。

最后的实操建议

就以这道题来说，我的做法已经固定下来了：拿到题先画柱状图，标出左墙、坑底、右墙三要素，再决定用哪种解法。单调栈的代码虽然只有十几行，但里面藏着的"触发结算""存下标而非高度""严格大于"这三个纪律，少一个都会在用例里翻车。你完全可以先照着本文代码跑通，然后把三个细节改成错误版本，亲眼看看报错长什么样——这比我苦口婆心说十遍都管用。等这题吃透了，84 题柱状图最大矩形，你会发现自己的思路顺得仿佛开挂。