接雨水

题目链接

接雨水

题目

给定一个整数数组 height 表示柱子的高度，其中宽度为 1，计算柱子之间能够接住多少雨水。

思路

使用双指针方法解决此问题。通过从两端向中间遍历数组，并更新左右两侧的最大高度，可以高效计算每个位置的存水量。双指针法利用了当前柱子的高度和左右两侧最大高度的对比，决定了水的存储量。

解题方法

1. 初始化指针和变量：

   • left 和 right 指针分别指向数组的两端（即 0 和 height.length - 1）。
   • leftMax 和 rightMax 分别记录从左到右和从右到左扫描时遇到的最大高度。
   • result 用于累加最终计算出的雨水量。

2. 遍历数组：

   • 使用 while (left < right) 循环，遍历数组，直到 left 和 right 指针相遇。
   • 在每次循环中，比较 leftMax 和 rightMax 的值：
     • 左侧较低 (leftMax < rightMax)：
       • 向右移动 left 指针 (left++)。
       • 更新 leftMax 为 leftMax 和 height[left] 中的较大值，表示更新左侧遇到的最大高度。
       • 计算当前位置的雨水量，即 leftMax - height[left]，并将其加到 result 中。如果当前高度 height[left] 小于 leftMax，说明当前位置能够接到雨水。
     • 右侧较低或相等 (leftMax >= rightMax)：
       • 向左移动 right 指针 (right--)。
       • 更新 rightMax 为 rightMax 和 height[right] 中的较大值，表示更新右侧遇到的最大高度。
       • 计算当前位置的雨水量，即 rightMax - height[right]，并将其加到 result 中。如果当前高度 height[right] 小于 rightMax，说明当前位置能够接到雨水。

3. 返回结果：

   • result 存储了整个数组中可以接到的总雨水量。

代码

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

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

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是数组的长度。双指针法确保每个位置只处理一次。
• 空间复杂度: $O(1)$，只使用了固定的额外空间。