42.接雨水

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= $2 * 10^4$
• 0 <= height[i] <= $10^5$

解析

双指针法：维护左右两侧的最大高度，每次移动较矮一侧的指针。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }
  return water;
};

双指针法的核心：对于每个位置，它能接的雨水量取决于其左右两侧最高柱子中较矮的那个。当 height[left] < height[right] 时，左侧的水量由 leftMax 决定。时间复杂度 O(n)，空间复杂度 O(1)。