当前位置：首页 > article >正文

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

article 2025/1/31 8:26:17

题目描述

给定 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），我们只需更新最大高度，而不需要计算水量。这是因为该柱子自身不能存储水，它只会影响后续的接水。
- 因此，这里用 >= 处理，确保即使遇到相等高度，也能正确更新最大高度，避免错误计算水量。