#42. 接雨水

LeetCode 原题链接

#题目描述

#1. 题型判断

本题要求计算每个位置上方能存多少水。

对于位置 i，它能接到的水量由左右两侧最高柱子的较小值决定：

water[i] = min(leftMax[i], rightMax[i]) - height[i]

如果提前维护左右两侧的最高值，就可以避免对每个位置都向两边扫描。

这题可以用两种常见方法：

• 双指针：从两端向中间收缩，维护 leftMax 和 rightMax，每次处理较矮的一侧。
• 单调栈：维护一个单调递减栈，当遇到更高柱子时，说明可以形成一个右边界，弹出低洼位置并结算水量。

#2. 指针含义

双指针解法使用闭区间 [left, right]：

• left：从数组左侧向右移动。
• right：从数组右侧向左移动。
• leftMax：left 左侧以及当前位置见过的最高柱子。
• rightMax：right 右侧以及当前位置见过的最高柱子。
• ans：累计接到的雨水总量。

关键判断：

• 如果 height[left] < height[right]，说明 left 位置右侧至少存在一个比它高的柱子，此时 left 能接多少水只取决于 leftMax。
• 否则处理 right，它能接多少水只取决于 rightMax。

单调栈解法中：

• 栈里保存柱子的下标。
• 栈底到栈顶对应的高度保持单调递减。
• 当前柱子 height[i] 如果高于栈顶柱子，说明栈顶可能是一个低洼位置，可以开始结算。

#3. 窗口或区间维护规则

#解法一：双指针

每轮比较 height[left] 和 height[right]：

• 如果 height[left] < height[right]：
  • 更新 leftMax = Math.max(leftMax, height[left])。
  • 当前 left 能接的水是 leftMax - height[left]。
  • 处理完后 left++。
• 否则：
  • 更新 rightMax = Math.max(rightMax, height[right])。
  • 当前 right 能接的水是 rightMax - height[right]。
  • 处理完后 right--。

为什么可以这样处理？

当 height[left] < height[right] 时，右侧已经有一个高度至少为 height[right] 的边界。对 left 来说，短板只可能是左侧最高柱子 leftMax。如果 leftMax 比当前位置高，就能接水；否则接不到水。

#解法二：单调栈

从左到右遍历每根柱子 i：

• 如果栈为空，或者 height[i] <= height[stack[stack.length - 1]]，直接把 i 入栈。
• 如果 height[i] > height[stack[stack.length - 1]]，说明出现了右边界：
  • 弹出栈顶 bottom，它是低洼位置。
  • 如果栈为空，说明没有左边界，不能接水。
  • 否则新的栈顶就是左边界 leftBoundary。
  • 宽度是 i - leftBoundary - 1。
  • 高度是 Math.min(height[leftBoundary], height[i]) - height[bottom]。
  • 水量为 width * boundedHeight。

#4. 答案更新时机

双指针解法中，每次处理 left 或 right 时，就可以立刻更新答案：

ans += leftMax - height[left];

或：

ans += rightMax - height[right];

单调栈解法中，只有当当前柱子比栈顶柱子高，并且弹出低洼位置后仍然存在左边界时，才更新答案。

#5. 边界条件与易错点

边界条件：

• 如果 height.length < 3，不足以形成左右边界，直接返回 0。
• 高度可以为 0，不需要特殊处理。
• 单调递增或单调递减数组都接不到水。

易错点：

• 双指针移动时，处理哪一侧取决于 height[left] 和 height[right] 的大小，不是 leftMax 和 rightMax 的大小。
• leftMax 和 rightMax 要先更新，再计算当前位置能接的水，保证结果不会为负数。
• 单调栈里建议存下标，不要只存高度，因为计算宽度需要下标。
• 单调栈弹出低洼位置后，如果栈为空，说明没有左边界，不能计算水量。
• 单调栈计算高度时要减去低洼柱子的高度：Math.min(leftHeight, rightHeight) - bottomHeight。

#6. 图解步骤

使用示例：

height = [4, 2, 0, 3, 2, 5]
index  =  0  1  2  3  4  5

下面分别展示两种方案的图解。图片负责呈现过程，表格负责对应代码里的关键状态。

#解法一：双指针过程

双指针每一步只结算较矮的一侧。

最终每个位置的接水量是：

index   0  1  2  3  4  5
height  4  2  0  3  2  5
water   0  2  4  1  2  0

所以总水量为：

0 + 2 + 4 + 1 + 2 + 0 = 9

#解法二：单调栈过程

单调栈保存下标，普通入栈不产生水量。只有当前柱子比栈顶高、触发弹栈时，才需要结算。

入栈过程：

有效结算过程：

弹出 0 后栈为空，说明没有左边界，所以不再产生水量。最终总水量也是 9。

#7. 代码实现

#解法一：双指针

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  if (height.length < 3) {
    return 0;
  }

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

  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      ans += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      ans += rightMax - height[right];
      right--;
    }
  }

  return ans;
};

#解法二：单调栈

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  const stack = [];
  let ans = 0;

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop();

      if (stack.length === 0) {
        break;
      }

      const leftBoundary = stack[stack.length - 1];
      const width = i - leftBoundary - 1;
      const boundedHeight =
        Math.min(height[leftBoundary], height[i]) - height[bottom];

      ans += width * boundedHeight;
    }

    stack.push(i);
  }

  return ans;
};

#8. 复杂度分析

双指针解法：

• 时间复杂度：O(n)，left 和 right 都只会向中间移动，每个位置最多处理一次。
• 空间复杂度：O(1)，只使用了常数个变量。

单调栈解法：

• 时间复杂度：O(n)，每个下标最多入栈一次、出栈一次。
• 空间复杂度：O(n)，最坏情况下栈中会保存所有柱子的下标。