42. 接雨水

力扣题目链接 (opens new window)

题目描述

给定 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

提示：

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

思路

接雨水这道题，到底应该按行计算，还是按列计算？

按行计算需要不断寻找一层水的左右边界，代码容易绕。按列计算更直观：宽度固定为 1，只需要求出每一列上方能接多高的水。

一列能接多少水

对于下标 i，它上方的雨水高度取决于：

• 左侧最高柱子 leftMax
• 右侧最高柱子 rightMax
• 当前柱子高度 height[i]

真正能装水的高度由较矮的边界决定：

当前列雨水 = min(leftMax, rightMax) - height[i]

例如某一列高度为 1，左侧最高柱子是 2，右侧最高柱子是 3，那么这一列能接：

min(2, 3) - 1 = 1

最直观的写法，是遍历每一列，再分别向左、向右寻找最高柱子。这样每一列都要扫描数组，时间复杂度是 O(n²)。

可以提前用两个数组记录每个位置的 leftMax 和 rightMax，把时间复杂度降到 O(n)，但需要 O(n) 的额外空间。

还能不能继续优化空间？

双指针为什么可行

我们让 left、right 分别从数组两端向中间移动，同时维护：

• leftMax：从左端到 left 位置见过的最高柱子
• rightMax：从右端到 right 位置见过的最高柱子

关键问题来了：每一步应该计算左边的柱子，还是右边的柱子？

如果 leftMax < rightMax，对于 left 这一列：

• 左侧最高柱子已经确定为 leftMax
• 右侧至少存在一根高度为 rightMax 的柱子
• 因为 rightMax 更高，所以这一列的水位一定由 leftMax 决定

此时不需要知道右侧还有没有更高的柱子，left 这一列的雨水已经可以确定：

leftMax - height[left]

计算完成后，left 向右移动。

同理，如果 leftMax >= rightMax，右侧较矮，right 这一列的雨水由 rightMax 决定：

rightMax - height[right]

计算完成后，right 向左移动。

哪一侧的最高边界更矮，就计算哪一侧，并移动哪一侧的指针。

由于 leftMax 和 rightMax 都包含当前柱子的高度，所以相减结果不会小于 0，不需要额外判断。

代码中遇到两侧最高边界相等时选择处理右侧。其实处理任意一侧都可以，只要整段逻辑保持一致。

模拟过程

以 height = [0,1,0,2,1,0,1,3,2,1,2,1] 为例。

初始化 left = 0、right = 11，更新得到 leftMax = 0、rightMax = 1。左侧边界更矮，所以第 0 列的雨水为 0 - 0 = 0，然后 left++。

此时 leftMax = 1、rightMax = 1。两侧边界相等，代码选择处理右侧：第 11 列雨水为 1 - 1 = 0，然后 right--。继续更新后，rightMax 变为 2。

现在 leftMax = 1 < rightMax = 2，左侧水位已经确定：

• 第 1 列接水 1 - 1 = 0
• 第 2 列接水 1 - 0 = 1

累计雨水量变为 1，left 移动到下标 3，此时 leftMax 更新为 2。

两侧最高边界再次相等，代码从右侧向内计算：

• 第 10 列接水 2 - 2 = 0
• 第 9 列接水 2 - 1 = 1
• 第 8 列接水 2 - 2 = 0

累计雨水量变为 2。right 移动到下标 7 后，rightMax 更新为 3。

接下来 leftMax = 2 < rightMax = 3，依次计算左侧剩余位置：

• 第 3 列接水 0
• 第 4 列接水 1
• 第 5 列接水 2
• 第 6 列接水 1

本轮增加 4 个单位，最终累计雨水量为 6。此时 left 与 right 在下标 7 相遇，循环结束。

解题代码

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int leftMax = 0;
        int rightMax = 0;
        int result = 0;

        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);

            if (leftMax < rightMax) {
                // 左边界更矮，当前左列的水位已经确定
                result += leftMax - height[left];
                left++;
            } else {
                // 右边界更矮或相等，当前右列的水位已经确定
                result += rightMax - height[right];
                right--;
            }
        }

        return result;
    }
};

复杂度分析

• 时间复杂度：O(n)。左右指针各自只遍历数组一次。
• 空间复杂度：O(1)。只使用常数个变量。

其他语言

Python3

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        result = 0

        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])

            if left_max < right_max:
                # 左边界更矮，当前左列的水位已经确定
                result += left_max - height[left]
                left += 1
            else:
                # 右边界更矮或相等，当前右列的水位已经确定
                result += right_max - height[right]
                right -= 1

        return result

Java

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int result = 0;

        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            if (leftMax < rightMax) {
                // 左边界更矮，当前左列的水位已经确定
                result += leftMax - height[left];
                left++;
            } else {
                // 右边界更矮或相等，当前右列的水位已经确定
                result += rightMax - height[right];
                right--;
            }
        }

        return result;
    }
}

Go

func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    result := 0

    for left < right {
        if height[left] > leftMax {
            leftMax = height[left]
        }
        if height[right] > rightMax {
            rightMax = height[right]
        }

        if leftMax < rightMax {
            // 左边界更矮，当前左列的水位已经确定
            result += leftMax - height[left]
            left++
        } else {
            // 右边界更矮或相等，当前右列的水位已经确定
            result += rightMax - height[right]
            right--
        }
    }

    return result
}

JS

var trap = function(height) {
    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let result = 0;

    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

        if (leftMax < rightMax) {
            // 左边界更矮，当前左列的水位已经确定
            result += leftMax - height[left];
            left++;
        } else {
            // 右边界更矮或相等，当前右列的水位已经确定
            result += rightMax - height[right];
            right--;
        }
    }

    return result;
};

与代码随想录联系

我在代码随想录的42. 接雨水中，从按列暴力计算、前后缀最高数组，一直讲到单调栈按行计算雨水。

Hot100 这里重点掌握双指针：哪一侧的最高边界更矮，就确定哪一侧的雨水。

和本题相关的内容：

• 11. 盛最多水的容器——同样从两端向中间移动，但求的是一个容器的最大面积
• 单调栈专题——从按列计算切换到按行计算，理解凹槽的高度和宽度
• 双指针学习路线——系统掌握数组与链表中的双指针题型