题干与适用场景
给定长度为 n 的非负整数数组 height，height[i] 表示第 i 根宽度为 1 的柱子高度。 计算这些柱子下雨后能接住的总水量。例如：
height = [4, 2, 0, 3, 2, 5]
结果 = 9目标是 O(n) 时间和 O(1) 额外空间。标准约束为 1 <= n <= 20000、 0 <= height[i] <= 100000；输入不含负高度，也不要求返回每一列的水量。
这道题有直接的公开面试证据：2025 年 6 月的一篇百度 Go 后端实习面经把“接雨水”记录为三道 现场手撕题之一；另一份公开电话面试记录还追加了“从指定位置倒入有限水量”的变体。力扣中英文 题面把它标为困难题，并同时列出数组、双指针、动态规划、栈和单调栈等标签。核心考查是从局部 公式推导线性算法并证明指针移动，因此分类为 coding，与实现语言和岗位方向无关。
面试官考察点
第一，能否先写出每一列的正确水量。第 i 列能达到的水面由左侧最高柱和右侧最高柱中较矮的 一根决定，而不是由相邻柱决定。若 leftMax[i] 与 rightMax[i] 都包含当前位置，则该列水量是 min(leftMax[i], rightMax[i]) - height[i]。
第二，能否把前后缀数组压缩为常数空间。保存所有位置的左右最高值很容易得到 O(n) 时间， 双指针进一步利用“较矮的已知边界已经足以确定一侧答案”，每轮只结算一列。
第三，是否真正理解移动规则。只背诵“移动较矮指针”不够；强回答会给出不变量，并分别讨论当前 柱子刷新边界和不刷新边界的情况，证明尚未扫描区域不会改变刚结算的水量。
最后，能否准确比较替代方案。前后缀数组最容易解释；单调栈按凹槽横向结算，适合相关栈题； 双指针最省空间。三种方法都可以是正确答案，但复杂度、证明方式和可扩展能力不同。
回答前需要澄清的问题
- 柱子宽度都为 1 吗？ 是；若宽度不同，每列的水深还要乘以对应宽度。
- 高度是否保证非负？ 是；负高度没有约定的物理含义，不能静默当作更深的坑。
- 空数组是否允许？ 标准约束不允许；本文实现对空数组自然返回
0，但接口契约仍应明确。 - 返回总量还是逐列结果？ 主问题只返回总量；逐列结果需要输出数组，因此空间至少为
O(n)。 - 是否必须达到常数额外空间？ 是；否则前后缀数组是更容易讲清楚的线性方案。
- 数值类型会溢出吗？ 应按真实约束估算上界；约束变化或使用较窄整数类型时要改用更宽累加器。
- 输入是一维高度图还是二维网格？ 本题是一维；二维接雨水需要从外边界向内扩展，算法不同。
- 是否允许修改输入？ 不需要，示范实现只读取
height。
30 秒回答框架
“某列的水量等于左右最高柱较小值减去本列高度。前后缀数组能在线性时间算出所有左右最高值， 但要 O(n) 空间。我用左右指针、leftMax 和 rightMax 压缩空间：它们分别记录已经扫描过的 左侧和右侧最高值。若 leftMax <= rightMax，右侧已知边界已经不低于 leftMax；左指针当前柱 若不刷新左界，水量就确定为 leftMax - height[left]，若刷新左界则水量为零。然后左指针右移； 另一侧完全对称。每列只处理一次，所以时间 O(n)、额外空间 O(1)。”
分步骤深入解答
第一步：先定义逐列答案。
令：
L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]因为 L[i] 和 R[i] 都包含 height[i]，两者都不会小于当前高度，所以公式不需要额外取零。 总水量是所有 water[i] 的和。这个公式也解释了为什么只看左右相邻柱会失败：远处更高的边界 可能决定整个凹槽的水面。
第二步：用基础方案建立正确基线。
| 方案 | 时间 | 额外空间 | 特点 | |---|---:|---:|---| | 每列向两侧扫描最高值 | O(n^2) | O(1) | 公式直接，但重复扫描 | | 前后缀最高值数组 | O(n) | O(n) | 最容易实现和证明 | | 单调递减栈 | O(n) | O(n) | 按凹槽横向结算宽度和深度 | | 双指针 | O(n) | O(1) | 每轮确定一侧的一列 |
前后缀方案先从左到右构造 L，再从右到左构造 R，最后套公式。双指针不是换了一套水量 定义，只是在尚未保存完整 L、R 时，利用已经足够的边界提前结算。
第三步：建立循环不变量。
每轮开始时维护：
left左侧的所有位置已经按逐列公式正确结算。right右侧的所有位置已经正确结算。leftMax是已扫描左区间height[0..left-1]的最大值；空区间取0。rightMax是已扫描右区间height[right+1..n-1]的最大值；空区间取0。water是所有已结算位置的水量和。
未处理区间始终是 [left, right]。每轮必须证明其中至少有一端可以永久结算，随后缩小这个区间。
第四步：证明为什么可以移动较小边界的一侧。
若 leftMax <= rightMax，考虑 height[left]：
- 若当前柱高于
leftMax，更新后它成为新的左侧最高柱。该列的左边界就是自身，水量为0。 - 若当前柱不高于
leftMax，真实右侧最高值至少为已经见到的rightMax，而
rightMax >= leftMax。因此左右边界较小值确定为 leftMax，该列水量正好是 leftMax - height[left]。
两种情况都不需要知道未扫描中间区域的具体形状，所以左列可以永久结算。若 leftMax > rightMax，对右列做完全对称的推理。这个证明也说明比较的是已知最高边界，不是简单 比较两个相邻柱或随意猜测哪边更低。
第五步：实现双指针。
def trap(height: list[int]) -> int:
left = 0
right = len(height) - 1
left_max = 0
right_max = 0
water = 0
while left <= right:
if left_max <= right_max:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water循环使用 left <= right，确保指针相遇时最后一列也会结算。先更新当前侧最高值再累加，既能让 新最高柱贡献零，也能保证差值非负。空数组时 right = -1，循环不执行并返回 0。
第六步：走查 [4, 2, 0, 3, 2, 5]。
处理位置 当前高度 结算侧 更新后边界 新增水量 累计
0 4 左 leftMax=4 0 0
5 5 右 rightMax=5 0 0
1 2 左 leftMax=4 2 2
2 0 左 leftMax=4 4 6
3 3 左 leftMax=4 1 7
4 2 左 leftMax=4 2 9右边的高度 5 为左侧剩余各列提供了足够高的已知边界，所以后续连续结算左侧。每列只出现一次， 不会按凹槽重复计水。
第七步：证明终止、正确性与复杂度。
初始化时两侧已处理区间都为空，不变量成立。第四步证明每轮新增的一列按逐列公式结算正确，且 更新后的 leftMax 或 rightMax 满足下一轮定义。每轮至少让 left 增加一或让 right 减少一， 所以有限步后 left > right；此时所有位置都已正确结算，总和正确。
每个位置只被访问一次，时间复杂度为 O(n)。除指针、两个边界和累加器外不分配随输入增长的 存储，额外空间为 O(1)。
第八步：用公式 oracle 和边界用例验证。
固定用例至少覆盖：单柱、两柱、全零、严格递增、严格递减、全等高、多个独立凹槽、平底凹槽、 标准示例，以及 [3, 0, 3]。最后一个用例能发现把循环误写成 left < right 而漏算相遇位置的错误。
再对短随机非负数组构造前后缀 L、R，用逐列公式作为 oracle，与双指针结果比较。同时检查结果 非负、镜像数组的总水量相同、在数组两端添加高度为零的柱子不改变原有总水量。随机差分用于发现 实现错误，正确性仍由不变量证明承担。
高质量示范回答
“我先把问题变成逐列计算：位置 i 的水深是 min(max(height[0..i]), max(height[i..n-1])) - height[i]。保存两个前后缀数组能做到 O(n) 时间和 O(n) 空间；若要求常数空间，我会用双指针。
循环中，leftMax 和 rightMax 分别记录指针外侧已经扫描过的最高柱。若 leftMax <= rightMax，我结算左指针：当前柱若刷新左界，水量为零；否则右侧已有的 rightMax 已经不低于左界，所以未知中间区域不可能把较小边界降到 leftMax 以下，该列水量确定 为 leftMax - height[left]。然后左指针右移。另一侧完全对称。
每轮永久处理一列，终止时所有列都被处理，因此总时间 O(n)；只保存常数个变量，额外空间 O(1)。我会测试空或短输入、单调数组、等高数组、多个凹槽和 [3, 0, 3]，并用前后缀公式对 随机小数组做差分验证。”
常见错误
- 用左右最高值中的较大者减当前高度 → 水会从较矮边界溢出 → 始终使用两侧最高值的较小者。
- 只比较相邻柱 → 远处边界被忽略 → 先写出包含整个左右区间的逐列公式。
- 先累加再更新当前侧最高值 → 新最高柱可能产生负水量 → 先更新边界，再计算非负差值。
- 循环写成
left < right→[3, 0, 3]的中间列可能未处理 → 让相遇位置也进入循环。 - 移动较大边界的一侧却不给证明 → 未知另一侧可能仍决定较小水面 → 只结算已有另一边界兜底的较小侧。
- 把“盛最多水的容器”公式套进来 →
宽度 × 边界高会把柱体和多个列重复计算 → 本题按每列水深求和。 - 说双指针每轮常数时间就结束分析 → 没有解释为什么答案不会被未来边界改变 → 给出边界不变量和两分证明。
- 声称单调栈空间也是
O(1)→ 严格单调输入可保存n个下标 → 准确写为最坏O(n)。 - 只跑一个标准示例 → 相遇、单调和等高边界未覆盖 → 加入固定用例和前后缀 oracle。
追问及应对
追问一：为什么不直接比较 height[left] 和 height[right]？
另一种正确写法可以比较两端当前高度，但它需要配套的不变量和更新顺序。本文比较 leftMax 与 rightMax，因为它们直接对应逐列公式中的边界。不能把一种写法的比较条件与另一种 写法的证明混在一起；面试时选择一套并保持代码、口述和证明一致。
追问二：如果要返回每一列接住的水量呢？
处理某列时把增量写入长度为 n 的结果数组，再求和或同时累加。时间仍为 O(n)，但输出本身需要 O(n) 空间。若调用方只消费流式结果，还要注意双指针的结算顺序不是从左到右，必须同时返回下标 或最后重排。
追问三：如果高度只能从左到右流式到达呢？
精确答案依赖未来的右边界，不能在固定内存下对每一列立刻定案。可以用单调栈保存尚未闭合的凹槽， 在更高右边界到达时结算；最坏仍需 O(n) 内存。若内存有硬上限，就要允许近似、外部存储或第二遍 扫描，不能继续承诺原问题的精确常数空间。
追问四：柱子宽度不同怎么办？
若第 i 根柱覆盖独立宽度 width[i]，边界高度逻辑不变，该列体积改为 waterDepth[i] * width[i]。若输入描述的是不规则横坐标和柱间空隙，则要先明确定义每段横向区间 的高度；不能直接把相邻中心点距离当成整根柱宽。
追问五：二维高度网格如何接雨水？
二维单元的水面由整个外边界约束，两个方向的指针不够。常用方案把所有边界格放入最小堆，每次 取当前最低边界向内扩展；较低邻格贡献高度差，并以两者较大值作为新的有效边界。配合访问标记， m × n 网格的时间为 O(mn log(mn))，空间为 O(mn)。
追问六：什么时候更适合用单调栈？
如果追问要求列出每个被左右边界闭合的凹槽、解释横向宽度，或继续转到柱状图矩形等单调栈模式， 栈方案更自然。它维护高度单调递减的下标；遇到更高柱时弹出凹槽底，使用新栈顶和当前柱作为左右 边界，按“有效宽度 × 新增水层高度”结算。总时间仍为 O(n)，最坏额外空间为 O(n)。