第3章｜栈与队列
Unit 13 · 综合加练：单调栈识别凹槽边界
← Unit 12
U13
Trapping Rain WaterBottom · Boundary · Layer
水不是在“低柱子”上产生，
而是在左右边界同时出现时被确定。
本单元把单调栈从“寻找下一个更大元素”推进到二维几何：当前更高柱到达时，弹出的索引是凹槽底部；新栈顶与当前索引构成左右边界；每次弹栈计算一层互不重叠的水。
LeetCode #42 题目模型Trapping Rain Water
题目要求
给定 n 个非负整数表示宽度均为 1 的柱子高度，计算这些柱子在下雨后能够接住多少单位的水。
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
pass
输入、输出与目标复杂度
- 输入：非负整数数组
height； - 输出：所有柱子之间可存储的水量总和；
- 本页主方法：单调栈，时间
O(n)，空间O(n)； - 迁移方法：双指针，时间
O(n)，空间O(1)。
示例
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
输出：6
输入：height = [4,2,0,3,2,5]
输出：9
输出：9
数据约束
n == height.length1 ≤ n ≤ 2 × 10⁴0 ≤ height[i] ≤ 10⁵
Valley Bottom
被当前更高柱弹出的索引。它是本次新水层的底部高度，而不是左边界。
Left Boundary
弹出底部后新的栈顶。若栈已空，说明左侧没有边界，本次不能形成封闭凹槽。
Bounded Height
min(left, right) - bottom。较矮边界决定水面高度。
Horizontal Layer
每次弹栈计算一层水：width × bounded_height，不同弹栈层互不重复。
Unit 12 → Unit 13｜从“关闭括号恢复父上下文”到“右边界到达结算历史凹槽”
Unit 12 · 上下文栈
左括号到达时保存尚未完成的父层状态；右括号是关闭事件，弹出最近父层并完成合并。
→
Unit 13 · 单调栈
下降柱高到来时保存尚未封闭的边界；更高右柱是关闭事件，弹出凹槽底部并完成水层结算。
共同设计方法：先定义“容器中的历史状态仍在等待什么”，再寻找使它离开容器的关闭事件。离开时，题目所需的信息必须已经完整。
认知任务 1
位置 2 的柱高为 0，它上方为什么能存 4 单位水？
先不要考虑算法。观察左右最高边界：水面只能达到两侧较矮者的高度，柱子自身占据的高度需要扣除。
主动画区单调栈凹槽实验
教学数组：[4, 2, 0, 3, 2, 5]蓝色区域表示当前已经确认的水层
未解决边界索引栈（栈底 → 栈顶）
本次弹栈计算
先读取柱子，再判断它是否能封闭此前的凹槽。
栈中高度保持单调不增；只有更高的当前柱才会触发弹栈。
current index2
stack size3
本层面积0
累计水量0
Read Bar
Compare Top
Pop Bottom
Find Left
Add Layer
Push Right
位置 2 的柱高为 0；左侧最高为 4，右侧最高为 5，因此该位置最终水深为 4。
逐位置重新寻找左右最高值相同前缀和后缀会被反复扫描
当前位置0
左扫描次数0
右扫描次数5
累计比较5
对位置 0，先向左和向右寻找最高柱；边缘位置无法储水，但仍进行了右侧扫描。
3 / 11
当前状态契约主要问题依赖当前动画状态
right / current2 / h=0
bottom—
left boundary0 / h=4
right boundary5 / h=5
bounded height4
total water9（最终）
核心不变量栈中索引对应的柱高从栈底到栈顶单调不增，并且这些索引仍未遇到足够高的右边界来完成所有水层计算。
为什么弹出的不是左边界？
弹出的柱子是凹槽底部；弹出之后暴露出的新栈顶才位于底部左侧。
为什么取较矮边界？
水会从较矮一侧溢出，因此水面不可能超过 min(left, right)。
位置 2 上方的最终水深是多少？左侧最高 4，右侧最高 5，当前柱高 0。
更小一步：先计算水面高度
min(4,5)，再减去柱高 0。代码补全：把凹槽边界编译为 PythonLeetCode 可直接提交格式
1from typing import List
2
3class Solution:
4 def trap(self, height: List[int]) -> int:
5 stack = []
6 water = 0
7
8 for right, current_height in enumerate(height):
9 while stack and :
10 bottom =
11 if :
12 break
13
14 left =
15 width =
16 bounded_height =
17 water +=
18
19 stack.append()
20
21 return water
提示 1｜容器保存什么？ stack 保存索引，因为需要同时访问柱高并计算左右宽度。 提示 2｜什么时候弹栈？ 只有 current_height 严格高于栈顶柱高，当前柱才可能成为新的右边界。 提示 3｜三种角色不能混淆 bottom = stack.pop() left = 弹栈后的 stack[-1] right = 当前扫描索引 提示 4｜面积公式 width = right - left - 1 bounded_height = min(height[left], current_height) - height[bottom] water += width * bounded_height 请回到填空区独立完成八个表达式。
代码与图像逐行联动点击代码行可跳转到对应状态
5stack = []
6water = 0
8for right, current_height in enumerate(height):
9while stack and current_height > height[stack[-1]]:
10bottom = stack.pop()
11if not stack:
12break
14left = stack[-1]
15width = right - left - 1
16bounded_height = min(...) - height[bottom]
17water += width * bounded_height
19stack.append(right)
21return water
right / current—
stack[]
bottom / left— / —
width—
bounded height—
water0
初始化空栈和累计水量。
完成代码联动 → 进入 LeetCode #11 原题迁移正确补全主代码或播放完整轨迹后解锁；查看提示与填入骨架不会跳过学习。
迁移题：LeetCode #11《盛最多水的容器》
先用 #42 的双指针异解理解“较矮一侧为什么可以被安全处理”，再迁移到一个新的官方问题：不再累加每个位置的雨水，而是在所有左右边界对中选择容量最大的一个容器。
从横向水层改为纵向逐点结算
#42 的单调栈保存未封闭凹槽；双指针只保存 left/right/left_max/right_max。比较两端后，较矮一侧的外部边界已经足够，当前位置可以立即结算。这个原则将成为 #11 贪心移动的认知起点。
#42 双指针执行轨迹教学数组 [4,2,0,3,2,5] · 最终 9
left / right0 / 5
left_max0
right_max0
本步增加0
累计水量0
决策比较两端
比较两端。较矮一侧可以依据该侧历史最大值结算当前位置。
1 / 7
LeetCode #11｜盛最多水的容器 · Medium
数组 · 双指针 · 贪心
官方题意
给定长度为 n 的数组 height。第 i 条垂线从 (i,0) 延伸到 (i,height[i])。选择两条垂线，与 x 轴构成不能倾斜的容器，返回它能够容纳的最大水量。
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
pass
官方样例与约束
输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
输入：height = [1,1]
输出：1
n == height.length2 ≤ n ≤ 10⁵0 ≤ height[i] ≤ 10⁴
读题检查 1｜题目最终返回什么？
#42 → #11｜相同的“较矮边界”，不同的目标函数
比较维度
#42 接雨水
#11 盛最多水的容器
选择对象
所有位置 / 所有水层都要累计
只选择一对左右边界
面积公式
位置水深或凹槽水层
min(hL,hR) × (R-L)移动依据
较矮一侧的位置可以安全结算
只移动较矮边界，才可能提高限制高度
输出
所有局部水量之和
遍历过程中出现的最大单个面积
结构判断｜为什么不能移动较高的一侧来寻找更优容器？
四个语义槽位｜把贪心证明编译成代码
Slot 1 · 状态双指针与最优值如何初始化？
Slot 2 · 当前候选当前容器面积公式是什么？
Slot 3 · 贪心移动每轮移动哪一侧？
Slot 4 · 输出循环结束后返回什么？
官方样例轨迹｜height = [1,8,6,2,5,4,8,3,7]
1 / 9
left / right0 / 8
边界高度1 / 7
宽度8
当前面积8
历史最大8
下一动作left += 1
当前输出候选：8
可选挑战｜脱离槽位独立重写 #11
检查器只验证双指针、面积公式、移动较矮边界和返回最大值，不会自动填入完整答案。
Unit 13 Skill 卡
看到“两个边界共同决定容量”时，先判断目标是累计所有局部容量，还是从所有边界对中选择一个全局最优。#42 需要计算所有凹槽水量；#11 只保留当前最大容器，并通过移动较矮边界排除不可能更优的候选。
主问题#42 · 单调栈横向水层
同题异解#42 · 双指针纵向结算
迁移原题#11 · 双指针贪心选边界对
共同瓶颈较矮边界限制水面 / 容器高度
#42 输出所有位置或水层之和
#11 输出单个边界对的最大面积
常见错误混淆累计量与最大值；移动较高侧
复杂度两种双指针均 O(n)/O(1)
后续迁移#407 二维接雨水 · 优先队列边界