Bloomberg 接雨水：双指针的边界证明与逐列体积

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入 n 个非负整数，每柱宽度 1，水不会从两端外侧封闭；返回总单位体积。
• 若原题为二维地形或可增删柱子，本方法不直接适用。

解题路线

1. 对每列 i，水量是 max(0,min(leftMax[i],rightMax[i])−height[i])；先给左右前缀数组 O(n) 空间的直观基线。
2. 双指针 left/right 向中间推进，同时维护已见左/右最高墙；当前较低一侧的水位由该侧最高墙确定，安全结算后移动。
3. 一侧高度等于另一侧时任选一致的并列方向；累计量用足够宽的整数类型。
4. 独立用小数组的前缀/后缀 oracle 穷举验证双指针，特别是高墙只在一侧、平坦、高低交错与空数组。

手动走一遍

高度 [4,2,0,3,2,5] 的逐列水量为 [0,2,4,1,2,0]，总 9；[0,1,0,2] 则中间低柱积 1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def trapped_water(heights):
    """Unit-width nonnegative bars; return total water volume."""
    if any(height < 0 for height in heights):
        raise ValueError("heights must be nonnegative")
    left, right = 0, len(heights) - 1
    left_max = right_max = total = 0
    while left <= right:
        if heights[left] <= heights[right]:
            left_max = max(left_max, heights[left])
            total += left_max - heights[left]
            left += 1
        else:
            right_max = max(right_max, heights[right])
            total += right_max - heights[right]
            right -= 1
    return total

复杂度

两个指针合计走 n 步，O(n) 时间、O(1) 附加空间；输出只是一个整数。

易错点与追问

容易失分的边界

• 用两端当前高度直接算水，却不维护迄今最大墙。
• 把当前柱自身加成水。
• 忘记端点无法蓄水。
• 总量类型溢出。

继续深挖

• 如何给出每列蓄水量？
• 动态更新某根柱高怎么维护总量？
• 二维接雨水为何需要优先队列/边界推进？