【数据结构与算法】力扣 42. 接雨水

题目描述

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

示例 1：

输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出： 6
解释： 上面是由数组 [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 * 104
• 0 <= height[i] <= 105

分析解答

双指针法解法：

我们使用左右两个指针来遍历数组，维护两个变量 left_max 和 right_max，分别记录从左边和右边柱子的最大高度。通过比较两边的最大高度，确定当前位置能够接到多少水。

原理就是水由左右两个高度最大的值来维护，而真正计算水又通过这二者间的小值来计算。

function trap(height) {if (height.length === 0) return 0;let left = 0;let right = height.length - 1;let left_max = 0;let right_max = 0;let totalWater = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= left_max) {left_max = height[left]; // 更新左边最高} else {totalWater += left_max - height[left]; // 计算左边可接水量}left++;} else {if (height[right] >= right_max) {right_max = height[right]; // 更新右边最高} else {totalWater += right_max - height[right]; // 计算右边可接水量}right--;}}return totalWater;
}// 测试
const height1 = [0,1,0,2,1,0,1,3,2,1,2,1];
const height2 = [4,2,0,3,2,5];
console.log(trap(height1)); // 输出 6
console.log(trap(height2)); // 输出 9

解释：

• left 和 right 指针分别从数组的两端向中间移动。
• 每次移动较低的一侧，并更新该侧的最大高度。
• 当前一侧高度小于该侧最大高度时，可以计算该位置能接的雨水。
• 最终，所有的雨水量累加在 totalWater 中。

这种解法的时间复杂度是 O(n)，空间复杂度是 O(1)，因为只使用了常数空间。

在这个双指针法解决“接雨水”问题的代码中，有几处涉及到“取等”和“不取等”的情况：

if (height[left] >= left_max) 和 if (height[right] >= right_max)：

• 含义：这两行代码分别是更新左右最大高度的条件。
• 取等 (>=)：这两个条件表示当前柱子高度如果大于或等于记录的最大高度，就更新最大高度。原因是：
  • 当 height[left] == left_max 或 height[right] == right_max，此时是无法接水的，因为水只能存储在比最大高度小的柱子位置上。如果当前柱子的高度和最大高度相同（即等于 left_max 或 right_max），我们只需更新最大高度，而不需要计算水量。这是因为该柱子自身不能存储水，它只会影响后续的接水。
  • 因此，这里用 >= 处理，确保即使遇到相等高度，也能正确更新最大高度，避免错误计算水量。

指针移动时的取等：

• 不取等：在 while (left < right) 中，两个指针的移动条件是 left < right。这里的不取等 (<) 确保指针不会交错或重叠，避免多次计算同一个位置。我们只希望指针在没有交错的情况下进行移动，因此使用严格小于号。

思路拓展