42. 接雨水

Bin大约 6 分钟

42. 接雨水

题目：接雨水

描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算它们能接住多少雨水。

示例：

示例 1:

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：在这种情况下，计算能接的雨水总量为 6。

示例 2:

输入：height = [4,2,0,3,2,5]
输出：9

解题思路：

问题的本质

给定一个数组，数组中的每个元素表示一个柱子的高度，每个柱子的宽度为 1。雨水只能积存在柱子之间的低洼区域中，我们需要计算柱子之间能够接住的雨水总量。

如何判断一个位置能接多少雨水？

在柱子 i 位置上能接的雨水量由以下公式决定：

rain[i] = min(maxHeightLeft, maxHeightRight) - height[i]

maxHeightLeft：柱子 i 左边的最高柱子的高度。
maxHeightRight：柱子 i 右边的最高柱子的高度。
height[i]：柱子 i 自身的高度。
解释公式：
柱子 i 上的雨水量是左右最高柱子中较矮的那个高度减去当前柱子的高度。如果 min(maxHeightLeft, maxHeightRight) <= height[i]，则雨水量为 0。

双指针法的思路

我们使用 双指针法，同时维护两侧的最大高度，避免对每个位置重复计算，从而优化时间复杂度。

步骤：

定义两个指针：
- 左指针 left 从数组的左端开始。
- 右指针 right 从数组的右端开始。
维护两侧最大高度：
- leftMax：左侧最高柱子的高度。
- rightMax：右侧最高柱子的高度。
计算每个位置的雨水量：
- 如果 height[left] < height[right]：
  - leftMax 决定了当前柱子 left 能接的雨水量。
  - 如果 height[left] < leftMax，则当前柱子能接的雨水量为 leftMax - height[left]。
  - 然后移动左指针 left++。
- 如果 height[left] >= height[right]：
  - rightMax 决定了当前柱子 right 能接的雨水量。
  - 如果 height[right] < rightMax，则当前柱子能接的雨水量为 rightMax - height[right]。
  - 然后移动右指针 right--。
循环结束条件：当 left 和 right 指针相遇时，停止循环。
结果：将所有柱子上能接的雨水量累加，返回总量。

举例分析

输入：`height = [0,1,0,2,1,0,1,3,2,1,2,1]`

我们一步步模拟双指针法：

初始状态：
- left = 0，right = 11，leftMax = 0，rightMax = 0，totalWater = 0
第一步：height[left] = 0，height[right] = 1
- height[left] < height[right]，更新 leftMax = max(0, height[left]) = 0。
- 当前雨水量为 leftMax - height[left] = 0 - 0 = 0。
- 移动左指针：left = 1。
第二步：height[left] = 1，height[right] = 1
- height[left] >= height[right]，更新 rightMax = max(0, height[right]) = 1。
- 当前雨水量为 rightMax - height[right] = 1 - 1 = 0。
- 移动右指针：right = 10。
第三步：height[left] = 1，height[right] = 2
- height[left] < height[right]，更新 leftMax = max(0, height[left]) = 1。
- 当前雨水量为 leftMax - height[left] = 1 - 1 = 0。
- 移动左指针：left = 2。
第四步：height[left] = 0，height[right] = 2
- height[left] < height[right]，更新 leftMax = max(1, height[left]) = 1。
- 当前雨水量为 leftMax - height[left] = 1 - 0 = 1。
- 积累雨水：totalWater = 1。
- 移动左指针：left = 3。
继续移动指针并计算：
- 按上述步骤继续计算每次能接的雨水，最终得到总量为 6。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] height = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            height[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        System.out.println(solution.trap(height));

        scanner.close();
    }
}

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;

        int left = 0, right = height.length - 1;  // 初始化指针
        int leftMax = 0, rightMax = 0;  // 记录两侧的最大高度
        int totalWater = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                // 左边较低，计算左边的雨水
                if (height[left] >= leftMax) {
                    leftMax = height[left];  // 更新左侧最大高度
                } else {
                    totalWater += leftMax - height[left];  // 接的雨水
                }
                left++;  // 移动左指针
            } else {
                // 右边较低，计算右边的雨水
                if (height[right] >= rightMax) {
                    rightMax = height[right];  // 更新右侧最大高度
                } else {
                    totalWater += rightMax - height[right];  // 接的雨水
                }
                right--;  // 移动右指针
            }
        }

        return totalWater;
    }
}

这是 双指针法 的核心逻辑，下面我详细解释 为什么要从较低的一侧计算雨水。

核心概念：雨水的计算依赖于较矮的那一侧

雨水的计算公式为：

rain[i] = min(maxHeightLeft, maxHeightRight) - height[i]

这意味着：

当前柱子 i 上的雨水量取决于柱子左边的最高柱子 (maxHeightLeft) 和右边的最高柱子 (maxHeightRight) 中较矮的那个。
因为水会从矮的一侧溢出，最终限制雨水量的永远是较矮的那一侧。

为什么从较低的一侧开始计算？

假设当前左右指针为 left 和 right，分别记录了两端的柱子，height[left] 和 height[right] 是对应柱子的高度。

情况 1：`height[left] < height[right]`

此时，height[left] 决定了当前可以接的水量，因为左边较低，右边的高度不会限制雨水量。
具体来说：
- 左侧的水量由 leftMax 决定，即 leftMax - height[left]。
- 因为左边较矮，所以无论右边的高度如何，都无法影响左边的积水。
- 因此，我们只需要考虑左边的柱子，移动左指针 left++，更新 leftMax。

情况 2：`height[left] >= height[right]`

此时，height[right] 决定了当前可以接的水量，因为右边较低，左边的高度不会限制雨水量。
具体来说：
- 右侧的水量由 rightMax 决定，即 rightMax - height[right]。
- 因为右边较矮，所以无论左边的高度如何，都无法影响右边的积水。
- 因此，我们只需要考虑右边的柱子，移动右指针 right--，更新 rightMax。