42 接雨水

一、题目

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

二、题解

对于下标 i 位置的柱子，它能够接到的雨水量取决于：

  • 左侧最高柱子的高度；
  • 右侧最高柱子的高度；
  • 当前柱子的高度。

当前柱子上方能够接到的雨水为：

min(左侧最高高度, 右侧最高高度) - 当前柱子的高度

因为水位由左右两侧较矮的柱子决定。

方法一：双指针

思路：双指针。

1. 核心思路

最直接的做法是记录每个位置左侧和右侧的最高柱子。

但是实际上，我们不需要把所有位置的最大值都保存下来，只需要使用两个变量：

leftMax：从左侧遍历过的柱子中的最大高度
rightMax：从右侧遍历过的柱子中的最大高度

同时使用两个指针：

left：从左向右移动
right：从右向左移动

核心思想是：

  • 如果 leftMax <= rightMax，左边当前柱子的接水量已经可以确定；
  • 如果 leftMax > rightMax，右边当前柱子的接水量已经可以确定；
  • 每次处理左右两侧最大高度中较小的一侧。

假设：

leftMax = 3
rightMax = 5

由于左侧最高柱子只有 3，即使右侧后面出现更高的柱子，左边的水位也只能达到 3。

因此左边当前柱子的接水量为：

leftMax - height[left]

2. 具体步骤

  1. 定义两个指针 left 和 right，分别指向数组的左右两端。
  2. 定义 leftMax 和 rightMax，记录左右两侧已经遍历过的最高柱子。
  3. 如果 leftMax <= rightMax：
    • 将左指针向右移动；
    • 更新 leftMax；
    • 计算当前位置能够接到的雨水。
  4. 否则：
    • 将右指针向左移动；
    • 更新 rightMax；
    • 计算当前位置能够接到的雨水。
  5. 当左右指针相遇时，返回累计的雨水量。

3. 关键逻辑

if (leftMax <= rightMax) {
    left++;

    // 更新左侧最高柱子
    leftMax = Math.max(leftMax, height[left]);

    // 计算当前左侧位置能够接到的雨水
    result += leftMax - height[left];
} else {
    right--;

    // 更新右侧最高柱子
    rightMax = Math.max(rightMax, height[right]);

    // 计算当前右侧位置能够接到的雨水
    result += rightMax - height[right];
}

解释：

  • 如果 leftMax <= rightMax，说明左侧是较低的一侧；
  • 当前左侧位置的水位一定由 leftMax 决定；
  • 因此可以直接计算左侧当前位置的雨水；
  • 如果 leftMax > rightMax，同理可以计算右侧当前位置的雨水。

更新最大值后再计算：

leftMax = Math.max(leftMax, height[left]);
result += leftMax - height[left];

这样可以保证：

leftMax >= height[left]

所以计算出的雨水量不会小于 0。

4. 代码

class Solution {
    public int trap(int[] height) {
        int n = height.length;

        // 少于 3 根柱子无法形成凹槽
        if (n < 3) {
            return 0;
        }

        // 左右双指针
        int left = 0;
        int right = n - 1;

        // 左右两侧已经遍历过的最高柱子
        int leftMax = height[left];
        int rightMax = height[right];

        // 记录总接水量
        int result = 0;

        while (left < right) {
            // 优先处理左右最高柱子中较低的一侧
            if (leftMax <= rightMax) {
                left++;

                // 更新左侧最高柱子
                leftMax = Math.max(leftMax, height[left]);

                // 当前柱子的接水量
                result += leftMax - height[left];
            } else {
                right--;

                // 更新右侧最高柱子
                rightMax = Math.max(rightMax, height[right]);

                // 当前柱子的接水量
                result += rightMax - height[right];
            }
        }

        return result;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：左右指针分别从数组两端向中间移动，每个位置最多被处理一次。

空间复杂度：O(1)O(1)

说明：只使用了若干变量，没有使用长度与输入规模相关的额外数组。

方法二：动态规划

思路：动态规划 / 前缀最大值与后缀最大值。

1. 核心思路

对于每个位置 i，需要知道：

leftMax[i]：位置 i 左侧，包括当前位置在内的最高柱子
rightMax[i]：位置 i 右侧，包括当前位置在内的最高柱子

当前位置的水位为：

min(leftMax[i], rightMax[i])

当前位置能够接到的雨水为：

min(leftMax[i], rightMax[i]) - height[i]

这种方法的核心是：

  • 从左向右计算每个位置的左侧最高高度；
  • 从右向左计算每个位置的右侧最高高度；
  • 根据左右最高高度中的较小值计算雨水。

因为 leftMax[i] 和 rightMax[i] 都包含当前位置，所以：

leftMax[i] >= height[i]
rightMax[i] >= height[i]

因此计算出的雨水量不会是负数。

2. 具体步骤

  1. 创建数组 leftMax，记录每个位置左侧的最高柱子。
  2. 创建数组 rightMax，记录每个位置右侧的最高柱子。
  3. 从左向右遍历，计算 leftMax。
  4. 从右向左遍历，计算 rightMax。
  5. 再次遍历数组，计算每个位置能够接到的雨水。
  6. 将所有位置的雨水量累加并返回。

3. 关键逻辑

leftMax[i] = Math.max(leftMax[i - 1], height[i]);

解释：

  • leftMax[i - 1] 是前一个位置左侧的最高柱子；
  • height[i] 是当前柱子的高度；
  • 两者中的最大值，就是当前位置左侧的最高柱子。

右侧最高柱子的计算方式同理：

rightMax[i] = Math.max(rightMax[i + 1], height[i]);

最终计算当前位置的雨水：

int waterLevel = Math.min(leftMax[i], rightMax[i]);
result += waterLevel - height[i];

解释：

  • 水位由左右两侧较矮的柱子决定；
  • 水位减去当前柱子的高度，就是当前位置的接水量。

4. 代码

class Solution {
    public int trap(int[] height) {
        int n = height.length;

        // 少于 3 根柱子无法形成凹槽
        if (n < 3) {
            return 0;
        }

        // leftMax[i] 表示位置 i 左侧（包括自己）的最高柱子
        int[] leftMax = new int[n];

        // rightMax[i] 表示位置 i 右侧（包括自己）的最高柱子
        int[] rightMax = new int[n];

        // 初始化最左侧位置
        leftMax[0] = height[0];

        // 从左向右计算左侧最高柱子
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // 初始化最右侧位置
        rightMax[n - 1] = height[n - 1];

        // 从右向左计算右侧最高柱子
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int result = 0;

        // 计算每个位置能够接到的雨水
        for (int i = 0; i < n; i++) {
            int waterLevel = Math.min(leftMax[i], rightMax[i]);
            result += waterLevel - height[i];
        }

        return result;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：分别进行了三次线性遍历，总时间复杂度仍然为 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：使用了长度为 n 的 leftMax 和 rightMax 数组。

方法三：单调栈

思路：单调栈。

1. 核心思路

前两种方法都是按照每根柱子竖直计算雨水，而单调栈是按照水平方向分层计算雨水。

栈中存储柱子的下标，并且保持从栈底到栈顶对应的柱子高度单调递减。

当遍历到一根比栈顶柱子更高的柱子时，说明找到了一个可以接水的凹槽。

此时：

当前柱子：凹槽的右边界
弹出的栈顶柱子：凹槽的底部
弹出后新的栈顶柱子：凹槽的左边界

凹槽能够接到的雨水为：

宽度 × 有效高度

其中：

宽度 = 右边界下标 - 左边界下标 - 1
有效高度 =
min(左边界高度, 右边界高度) - 凹槽底部高度

2. 具体步骤

  1. 创建一个栈，用于存储柱子的下标。
  2. 从左向右遍历所有柱子。
  3. 当当前柱子高于栈顶柱子时：
    • 弹出栈顶，将其作为凹槽底部；
    • 如果栈为空，说明没有左边界，不能接水；
    • 将新的栈顶作为左边界；
    • 将当前柱子作为右边界；
    • 计算凹槽的宽度和有效高度；
    • 累加这一层的雨水量。
  4. 将当前柱子的下标压入栈中。
  5. 遍历结束后返回结果。

3. 关键逻辑

while (!stack.isEmpty()
        && height[right] > height[stack.peek()]) {

    // 弹出凹槽底部
    int bottom = stack.pop();

    // 没有左边界，无法形成凹槽
    if (stack.isEmpty()) {
        break;
    }

    // 弹出底部后，新的栈顶是左边界
    int left = stack.peek();

    // 左右边界之间的水平宽度
    int width = right - left - 1;

    // 水位由左右边界中较矮的一侧决定
    int boundedHeight =
            Math.min(height[left], height[right])
                    - height[bottom];

    result += width * boundedHeight;
}

解释：

  • 当前柱子比栈顶柱子高，说明栈顶柱子的右侧出现了更高的边界；
  • 弹出的柱子可以作为凹槽底部；
  • 弹出后新的栈顶是左边界；
  • 当前柱子是右边界；
  • 根据左右边界的较小高度计算这一层雨水的高度。

例如：

柱子高度：[3, 1, 2]

当遍历到高度为 2 的柱子时：

左边界高度 = 3
凹槽底部高度 = 1
右边界高度 = 2

宽度为：

2 - 0 - 1 = 1

有效高度为：

min(3, 2) - 1 = 1

因此接水量为：

1 × 1 = 1

4. 代码

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int trap(int[] height) {
        // 记录总接水量
        int result = 0;

        // 栈中存储柱子的下标
        // 对应的柱子高度从栈底到栈顶单调递减
        Deque<Integer> stack = new ArrayDeque<>();

        for (int right = 0; right < height.length; right++) {

            // 当前柱子高于栈顶柱子，说明可能形成凹槽
            while (!stack.isEmpty()
                    && height[right] > height[stack.peek()]) {

                // 弹出的柱子作为凹槽底部
                int bottom = stack.pop();

                // 栈为空说明没有左边界，无法接水
                if (stack.isEmpty()) {
                    break;
                }

                // 新的栈顶柱子作为左边界
                int left = stack.peek();

                // 左右边界之间的宽度
                int width = right - left - 1;

                // 当前这一层雨水的有效高度
                int boundedHeight =
                        Math.min(height[left], height[right])
                                - height[bottom];

                // 累加当前凹槽这一层的雨水
                result += width * boundedHeight;
            }

            // 当前柱子入栈
            stack.push(right);
        }

        return result;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：虽然代码中存在嵌套循环，但是每个柱子最多入栈一次、出栈一次，因此总时间复杂度为 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：最坏情况下，所有柱子都按照单调递减顺序排列，所有下标都会进入栈中。

评论