42. Trapping Rain Water

42. Trapping Rain Wateropen in new window

🔴 🔖 栈 数组 双指针 动态规划 单调栈 🔗 LeetCodeopen in new window

题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

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

题目大意

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

解题思路

思路一：动态规划

对于接雨水问题，我们的目标是找到每个位置上可以蓄水的量，然后将这些蓄水量加起来得到最终的结果。

在这个问题中，蓄水量取决于当前位置的左侧最大高度和右侧最大高度。因此可以考虑预处理数组，计算每个位置的左侧最大高度和右侧最大高度，然后在遍历数组时，通过这两个值来计算蓄水量。

初始化左侧最大高度数组 leftMax：
- 从左到右遍历数组，对于每个位置 i，leftMax[i] 存储位置 i 左侧（包括位置 i）的最大高度。
初始化右侧最大高度数组 rightMax：
- 从右到左遍历数组，对于每个位置 i，rightMax[i] 存储位置 i 右侧（包括位置 i）的最大高度。
遍历数组计算蓄水量：
- 对于每个位置 i，蓄水量等于 min(leftMax[i], rightMax[i]) - height[i]，其中 height[i] 是当前位置的高度。
- 注意，如果 min(leftMax[i], rightMax[i]) - height[i] 小于等于零，则当前位置不会蓄水。
将所有位置的蓄水量相加得到最终结果。

这种方法的关键在于预处理左侧和右侧最大高度数组，使得在计算蓄水量时能够直接使用这两个数组的值，而无需每次都重新计算。时间复杂度为 O(n) ，空间复杂度为 O(n) ，其中 n 是数组的长度。

思路二：双指针

动态规划的做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。是否可以将空间复杂度降到 O(1) ？

注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。

初始化：定义两个指针 left 和 right ，分别指向数组的开头和结尾。使用两个变量 leftMax 和 rightMax 分别记录左侧和右侧的最大高度，初始化为 0。
循环遍历：在每次循环中，比较 height[left] 和 height[right] ，选择较小的一方，根据这一方的高度来更新 leftMax 或 rightMax 。然后，根据当前的 leftMax 和 rightMax 计算当前位置上的蓄水量。
- 如果 height[left] < height[right] ，则必有 leftMax < rightMax，下标 left 处能接的雨水量等于 leftMax − height[left] ，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；
- 如果 height[left] ≥ height[right]，则必有 leftMax ≥ rightMax，下标 right 处能接的雨水量等于 rightMax − height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）。

这个算法的时间复杂度是 O(n)，其中 n 是数组的长度，因为我们只需遍历一次数组。空间复杂度是 O(1)，因为只使用了常数额外空间。

代码

动态规划

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  const n = height.length;
  // 左侧最大高度数组
  let leftMax = [height[0]];
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(height[i], leftMax[i - 1]);
  }

  // 右侧最大高度数组
  let rightMax = [];
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(height[i], rightMax[i + 1]);
  }

  // 遍历数组计算蓄水量
  let res = 0;
  for (let i = 0; i < n - 1; i++) {
    res += Math.min(leftMax[i], rightMax[i]) - height[i];
  }
  return res;
};

双指针

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

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

42. Trapping Rain Water

# 42. Trapping Rain Wateropen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：动态规划

# 思路二：双指针

# 代码

# 相关题目

42. Trapping Rain Wateropen in new window

题目

题目大意

解题思路

思路一：动态规划

思路二：双指针

代码

相关题目