接雨水：边界不变量与二维扩展

接雨水：边界不变量与二维扩展

从逐列水量推导前后缀与双指针解法，再理解二维地形的最低漏水边界。动态规划的一般定义见动态规划基础，这里集中讨论水位由什么边界决定。

1. 每一列到底能放多少水

输入 height 是非负整数数组，每根柱子的宽度为 1。水只能留在有左右边界的凹槽中，求所有列的水量之和。以下实现假设高度与总水量都在 JavaScript 安全整数范围内，不修改输入；若业务输入允许负数、非整数或超大整数，应先约束数据或另用 BigInt 实现。

对下标 i，定义包含当前列的两个最大值：

leftMax[i]  = max(height[0..i])
rightMax[i] = max(height[i..n-1])
water[i]    = min(leftMax[i], rightMax[i]) - height[i]

左右较矮的最高边界决定最终水位。最大值包含当前列，所以差值不会为负；若定义改成“不含当前列”，就必须再用 max(0, ...) 截断。最左、最右两列的水量自然为 0。

输入	每列水量	总水量
[0,1,0,2,1,0,1,3,2,1,2,1]	[0,0,1,0,1,2,1,0,0,1,0,0]	6
[4,2,0,3,2,5]	[0,2,4,1,2,0]	9

可以在接雨水分步演示中观察双指针、已知边界与逐列累加过程。

2. 从暴力扫描到前后缀缓存

2.1 暴力：每列各找一次左右最高点

function trapBruteForce(height) {
  let total = 0

  for (let i = 1; i < height.length - 1; i += 1) {
    let leftMax = height[i]
    let rightMax = height[i]
    for (let left = 0; left < i; left += 1) {
      leftMax = Math.max(leftMax, height[left])
    }
    for (let right = i + 1; right < height.length; right += 1) {
      rightMax = Math.max(rightMax, height[right])
    }
    total += Math.min(leftMax, rightMax) - height[i]
  }

  return total
}

每列扫描两侧，时间复杂度为 O(n^2)，额外空间为 O(1)。大量扫描重复经过相同柱子，正是缓存可以消掉的工作。

2.2 前后缀：每个最大值只算一次

先从左向右递推 leftMax[i] = max(leftMax[i - 1], height[i])，再从右向左递推 rightMax。两张表的边界分别是首、尾柱高。

function trapWithPrefixSuffix(height) {
  const n = height.length
  if (n < 3) return 0

  const leftMax = new Array(n)
  const rightMax = new Array(n)
  leftMax[0] = height[0]
  rightMax[n - 1] = height[n - 1]

  for (let i = 1; i < n; i += 1) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i])
  }
  for (let i = n - 2; i >= 0; i -= 1) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i])
  }

  let total = 0
  for (let i = 1; i < n - 1; i += 1) {
    total += Math.min(leftMax[i], rightMax[i]) - height[i]
  }
  return total
}

三次线性遍历仍是 O(n) 时间，两个长度为 n 的数组占 O(n) 额外空间。这里递推的是“前缀/后缀最大值”状态，不能仅凭题目被归类为 DP 就跳过状态定义。

3. 双指针为什么可以提前结算一侧

维护尚未结算的区间 [left, right]。每轮先把两端柱高纳入对应最大值：leftMax 是 [0, left] 的最大值，rightMax 是 [right, n - 1] 的最大值。

• 若 leftMax <= rightMax，左端 left 已经找到不低于 leftMax 的右侧屏障。中间即使还藏着更高的柱子，也不可能把这一列水位降到 leftMax 以下，因此可确定它的水量是 leftMax - height[left]。
• 若 leftMax > rightMax，同理可结算右端 right，水量为 rightMax - height[right]。

这段证明用的是两侧已经见过的最高边界，与代码比较的变量一致。不要把判断条件换成当前柱高后仍直接套用这段不变量。

function trapWithTwoPointers(height) {
  if (height.length < 3) return 0

  let left = 0
  let right = height.length - 1
  let leftMax = 0
  let rightMax = 0
  let total = 0

  while (left <= right) {
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])

    if (leftMax <= rightMax) {
      total += leftMax - height[left]
      left += 1
    } else {
      total += rightMax - height[right]
      right -= 1
    }
  }

  return total
}

每轮只结算一个位置，然后收缩区间；相遇时那一列也只结算一次。累计恰好 n 轮，时间为 O(n)，额外空间为 O(1)。当两侧最大值相等时，两侧都已具备充分的对侧屏障，任选一侧推进即可；此实现固定推进左侧。

4. 二维地形不能只找四条直线的最高点

二维题的输入是矩形高度图，每格面积为 1，水通过上下左右相邻的格子流动，地图外部不蓄水。它有时也被称为“3D 接雨水”，但输入仍是二维网格，高度是第三个几何维度。

下面的地形中，所有 0 都通过一条拐弯通道连到右侧边界，所以实际蓄水量为 0：

5 5 5 5 5
5 5 0 0 5
5 5 0 5 5
5 5 0 0 0  -> 外部
5 5 5 5 5

以从 0 开始计数的 (2, 2) 为例，它的上、下、左、右四条直线都能遇到高度 5，但水可以沿 (2,2) -> (3,2) -> (3,3) -> (3,4) 流出。四方向最大值会错误地认为这一格能蓄 5 单位水。

真正决定水位的是通往任意边界的所有路径中，所需跨越的最高地形的最小值。这是路径问题，不能把一维左右边界公式机械扩展成四条直线。

5. 从最低边界向内扩张

把地图全部边界加入小顶堆，按“有效边界高度”从低到高弹出：

1. 弹出最低边界格，记有效高度为 level。
2. 对未访问的相邻格，其原始高度为 h，新增水量为 max(0, level - h)。
3. 将相邻格以 max(level, h) 入堆。低洼格被水填平后，继续向内传播的边界是水位，不能退回原始地面高度。

堆操作沿用数组表示完全二叉树、上浮和下沉的写法，基础结构见JavaScript 数据结构；这里的键是格子的 level，与 TopK 按数值筛选的用途不同。下面两个代码块一起运行即可。

class BoundaryMinHeap {
  heap = []

  insert(cell) {
    const heap = this.heap
    heap.push(cell)
    let index = heap.length - 1
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2)
      if (heap[parent].level <= heap[index].level) break
      ;[heap[parent], heap[index]] = [heap[index], heap[parent]]
      index = parent
    }
  }

  extractMin() {
    const heap = this.heap
    if (heap.length === 0) return null
    const minimum = heap[0]
    const last = heap.pop()
    if (heap.length === 0) return minimum
    heap[0] = last

    let index = 0
    while (true) {
      const left = index * 2 + 1
      const right = left + 1
      let smallest = index
      if (left < heap.length && heap[left].level < heap[smallest].level) smallest = left
      if (right < heap.length && heap[right].level < heap[smallest].level) smallest = right
      if (smallest === index) break
      ;[heap[index], heap[smallest]] = [heap[smallest], heap[index]]
      index = smallest
    }
    return minimum
  }
}

function trapRainWater2D(heightMap) {
  const rows = heightMap.length
  if (rows === 0) return 0
  const columns = heightMap[0].length
  if (heightMap.some((row) => row.length !== columns)) {
    throw new TypeError('heightMap must be rectangular')
  }
  if (rows < 3 || columns < 3) return 0

  const visited = Array.from({ length: rows }, () => new Array(columns).fill(false))
  const boundary = new BoundaryMinHeap()
  const addBoundary = (row, column) => {
    if (visited[row][column]) return
    visited[row][column] = true
    boundary.insert({ row, column, level: heightMap[row][column] })
  }
  for (let row = 0; row < rows; row += 1) {
    addBoundary(row, 0)
    addBoundary(row, columns - 1)
  }
  for (let column = 0; column < columns; column += 1) {
    addBoundary(0, column)
    addBoundary(rows - 1, column)
  }

  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  let total = 0
  while (boundary.heap.length > 0) {
    const { row, column, level } = boundary.extractMin()
    for (const [dr, dc] of directions) {
      const nextRow = row + dr
      const nextColumn = column + dc
      if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns) continue
      if (visited[nextRow][nextColumn]) continue

      visited[nextRow][nextColumn] = true
      const height = heightMap[nextRow][nextColumn]
      total += Math.max(0, level - height)
      boundary.insert({ row: nextRow, column: nextColumn, level: Math.max(level, height) })
    }
  }
  return total
}

二维输入同样约定为非负安全整数，且总水量不超过安全整数范围；代码额外检查矩形，不改变原地形。空矩阵、空行以及少于三行或三列都无法形成内部蓄水格，返回 0。

5.1 为什么入堆就可以标记访问

堆中 level 表示该格已找到的、通往外边界的最低可达水位。当前弹出的 level 最小；若相邻格高度 h <= level，通过它到达外部的水位已可确定为 level，未来从不更低的边界进入不会变得更优。若 h > level，任何路径都必须跨越它自己的高度 h，当前候选 h 已经达到下界。

因此第一次从最低边界发现相邻格时，它的有效高度 max(level, h) 就已经确定，可以立即标记访问、计水并入堆。这样还能防止同一格从多个方向重复计水，边界四角也只会入堆一次。这依赖本题的 max(level, h) 转移，不能照搬为“一般带权最短路都能入队即确认最优”。

5.2 复杂度和样例

设网格有 m * n 格，每格入堆和出堆各一次，时间复杂度为 O(mn log(mn))，堆和访问矩阵占 O(mn) 空间。

trapRainWater2D([
  [1, 4, 3, 1, 3, 2],
  [3, 2, 1, 3, 2, 4],
  [2, 3, 3, 2, 3, 1],
]) // 4

trapRainWater2D([
  [3, 3, 3, 3],
  [3, 0, 0, 3],
  [3, 0, 0, 3],
  [3, 3, 3, 3],
]) // 12

6. 边界与面试追问

情况或追问	应说明的结论
一维长度小于 3、全零、单调递增或递减	都返回 0；不能构成有高度差的凹槽
两端相等，如 [2,0,2]	水量为 2，双指针等高时仍须推进一侧
平台，如 [3,3,3]	水量为 0，相等高度不会自行产生空间
大凹槽，如 [5,0,0,5]	每列分别累计，共 10，不能只取一次高度差
是否可以排序	不可以，排序会改变地形的相邻关系
双指针的空间为何是常数	只维护下标、边界高度与总量；演示程序额外保存帧是可视化开销，不属于算法本身
二维为什么不用普通 FIFO BFS	FIFO 按步数扩展，无法保证先处理最低漏水边界
二维为什么不能把原始高度入堆	低洼格会把已经确认的水位错误地降低，后续蓄水会被低估

验证时，一维可将多种实现与逐层填水的独立判定比较；二维可按每个整数水层从外部进行连通性搜索，核验常见样例、封闭盆地以及拐弯泄水反例。