题目描述
给一排柱子的高度，下雨后能接多少格水？
思路解析
看清地形：高度是 3、0、2、0、4。中间凹下去的地方能存水，关键是要有「左墙」和「右墙」把水夹住。
栈里存柱子的下标，并且让对应高度从栈底到栈顶越来越矮。一旦遇到一根更高的柱子，就说明「右墙」来了，可以接水了。
i = 0 · 高 3：栈是空的，直接把下标 0 入栈。栈：[0]。
i = 1 · 高 0：高度 0 比栈顶（下标0，高3）矮，符合「递减」，入栈。栈：[0, 1]。
i = 2 · 高 2：高度 2 比栈顶（下标1，高0）高！这说明下标 1 这个坑的右墙出现了，可以接水。
i = 2 · 算这格水：弹出坑底下标 1。它的左墙是新栈顶（下标0，高3），右墙是当前（下标2，高2）。能接的水 = (min(3,2) − 0) × 宽1 = 2 格。
i = 2 · 入栈：现在高度 2 比新栈顶（高3）矮了，把下标 2 入栈。栈：[0, 2]。
i = 3 · 高 0：高度 0 比栈顶矮，入栈。栈：[0, 2, 3]。
i = 4 · 高 4：高度 4 比栈顶（下标3，高0）高，右墙来了。注意：4 很高，可能要连续接好几层，咱一层一层来。
i = 4 · 第①层 · 弹坑底：弹出坑底下标 3。它的左墙是下标2(高2)、右墙是下标4(高4)。接水 = (min(2,4)−0) × 宽1 = 2。累计 4。
i = 4 · 还更高吗？：弹完后看新栈顶是下标2(高2)。当前 4 还是比它高，说明还能再接一层，继续弹。
i = 4 · 第②层 · 弹坑底：弹出坑底下标 2。左墙下标0(高3)、右墙下标4(高4)，宽 3、高 min(3,4)−2=1，接水 3。累计 7。
i = 4 · 还更高吗？：新栈顶是下标0(高3)。当前 4 还比它高，再弹一次。
i = 4 · 弹到栈空：弹出下标0后栈空了——没有左墙，水就接不住了，本轮停止。
i = 4 · 入栈：最后把当前下标 4 自己入栈。它成了新的「左墙候选」。
结束：所有柱子处理完，总共接住 7 格水。蓝色就是积水。
单调栈的套路：每来一个新元素，就把栈里「比它矮/小」的旧元素结算掉。每日温度、下一个更大元素都是同款。
参考代码（Python）
1def trap(self, height):
2 stack = list() # 存下标，高度递减
3 result = 0
4 for i, h in enumerate(height):
5 while stack and h > height[stack[-1]]: # 右墙更高 → 接水
6 bottom = stack.pop() # 坑底
7 if not stack: break # 没有左墙了
8 left = stack[-1] # 左墙
9 w = i - left - 1 # 宽
10 h2 = min(height[left], h) - height[bottom] # 高
11 result += w * h2
12 stack.append(i)
13 return result复杂度分析
- 时间复杂度：O(n) —— 每个下标进出栈各一次
- 空间复杂度：O(n) —— 栈最多存 n 个下标
套路模板
维持栈内递减；每来一个更大的，就把栈里比它小的一一弹出结算。
1# 遇到更大就结算
2stack = []
3for i in range(n):
4 while stack and a[i] > a[stack[-1]]:
5 top = stack.pop()
6 if not stack: break
7 宽 = i - stack[-1] - 1
8 高 = min(a[stack[-1]], a[i]) - a[top]
9 stack.append(i)易错点
- ❌ 弹出后不判栈空就取 stack[-1] → ✅ if not stack: break（没有左墙就没法接水）
- ❌ 宽度写成 i - top → ✅ 宽 = i - stack[-1] - 1（宽是左右墙之间的距离，不含墙本身）
- ❌ 高度忘了减坑底 → ✅ 高 = min(a[左], a[i]) - a[top]（要扣掉坑底已有的高度）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。