42. 接雨水

🔴   🔖  栈 数组 双指针 动态规划 单调栈  🔗 力扣 LeetCode

题目

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 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解题思路

思路一：动态规划

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

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

1. 初始化左侧最大高度数组 leftMax：

   • 从左到右遍历数组，对于每个位置 i，leftMax[i] 存储位置 i 左侧（包括位置 i）的最大高度。

2. 初始化右侧最大高度数组 rightMax：

   • 从右到左遍历数组，对于每个位置 i，rightMax[i] 存储位置 i 右侧（包括位置 i）的最大高度。

3. 遍历数组计算蓄水量：

   • 对于每个位置 i，蓄水量等于 min(leftMax[i], rightMax[i]) - height[i]，其中 height[i] 是当前位置的高度。
   • 注意，如果 min(leftMax[i], rightMax[i]) - height[i] 小于等于零，则当前位置不会蓄水。

4. 将所有位置的蓄水量相加得到最终结果。

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

---

思路二：双指针

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

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

1. 初始化：定义两个指针 left 和 right ，分别指向数组的开头和结尾。使用两个变量 leftMax 和 rightMax 分别记录左侧和右侧的最大高度，初始化为 0。

2. 循环遍历：在每次循环中，比较 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;
};

相关题目

题号	标题	题解	标签	难度
11	盛最多水的容器	[✓]	贪心 数组 双指针
238	除自身以外数组的乘积	[✓]	数组 前缀和
407	接雨水 II		广度优先搜索 数组 矩阵 1+
755	倒水 🔒		数组 模拟
2874	有序三元组中的最大值 II		数组