LeetCode 42：接雨水（Trapping Rain Water）题解

Trapping Rain Water 是 LeetCode Hot 100 里面一道非常经典的数组题。

这道题在 LeetCode 里知名度非常高，因为它表面上看起来像是一道简单的“算面积”题，但真正做起来时，很多人都会卡在一个问题上：

某个位置到底能接多少水，应该怎么判断？

如果只是看某一根柱子的高度，其实是没法直接算出它上面能存多少水的。 因为能不能接住水，不仅取决于它自己，还取决于它左边最高的柱子和右边最高的柱子。

你给出的这份 Java 代码，使用的是这道题最经典、也最容易理解的一种解法：

动态规划预处理左右最大值

这种写法的核心思路非常清晰：

1. 先预处理每个位置左边最高的柱子

2. 再预处理每个位置右边最高的柱子

3. 最后根据“短板原理”计算每个位置能存多少水

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给定 n 个非负整数，表示一个柱状图中每根柱子的高度，柱子的宽度都为 1。

现在下雨了，问这个柱状图最多能接多少雨水。

例如数组：

height = [0,1,0,2,1,0,1,3,2,1,2,1]

表示从左到右每个位置柱子的高度。

下雨之后，某些低洼位置会存下雨水，最终总共可以接住的雨水量是：

6

这道题的关键不是画图，而是理解：

某一个位置上方能装多少水。

示例

示例 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

这个例子里也有多个凹槽，最终总共可以接住 9 单位的水。

这道题最关键的观察是什么？

这道题真正的核心，其实只有一句话：

某个位置能接多少水，只取决于它左边最高柱子和右边最高柱子中较矮的那个。

为什么？

因为水想要存住，必须左右两边都得有“墙”。

假设当前位置是 i：

• 左边最高柱子高度是 leftMax[i]

• 右边最高柱子高度是 rightMax[i]

那么当前位置最终水位的上限就是：

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

因为水位不可能超过较矮的那一边。

然后再减去当前位置柱子本身的高度 height[i]，就得到当前位置真正能存的水量：

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

只要这个值大于 0，说明这里可以接水；否则就接不了。

这就是整道题的本质。

最直接的暴力思路

如果我们先不考虑优化，可以对每个位置都做下面的事情：

1. 往左扫描，找左边最高柱子

2. 往右扫描，找右边最高柱子

3. 取较小值减去当前高度

4. 累加结果

这个方法当然是可行的，但时间复杂度会比较高。

假设数组长度是 n：

• 对每个位置都要往左找一次、往右找一次

• 每次扫描最坏是 O(n)

所以总时间复杂度会变成：

O(n^2)

这显然不够高效。

于是我们就会想到：

左边最大值和右边最大值是不是可以提前算好？

这正是你这段代码的思路。

核心思路：预处理左右最大值

你的代码本质上分成三步：

第一步：预处理 leftMax

leftMax[i] 表示：

从下标 0 到下标 i 这个范围内的最高柱子高度。

第二步：预处理 rightMax

rightMax[i] 表示：

从下标 i 到下标 n-1 这个范围内的最高柱子高度。

第三步：逐个位置计算雨水量

对于每个位置 i：

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

最后把所有位置的雨水量加起来，就是答案。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

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

        // 特殊情况：空数组无法接水
        if (n == 0) return 0;

        // leftMax[i] 表示位置 i 左侧（包含自己）最高的柱子
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // rightMax[i] 表示位置 i 右侧（包含自己）最高的柱子
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 统计总雨水量
        int totalWater = 0;
        for (int i = 0; i < n; i++) {
            totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return totalWater;
    }
}

代码拆解

这段代码整体不长，但思路很完整。 下面一步一步来看。

1. 为什么空数组直接返回 0？

if (n == 0) return 0;

因为如果没有柱子，自然就不可能形成凹槽，也就接不到任何雨水。

这是一个很基础但不能漏掉的边界情况。

2. leftMax 数组到底表示什么？

int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}

这里的 leftMax[i] 表示：

从左边走到当前位置 i 为止，见过的最高柱子。

比如：

height = [0,1,0,2,1]

那么：

leftMax = [0,1,1,2,2]

解释一下：

• leftMax[0] = 0

• leftMax[1] = max(0,1) = 1

• leftMax[2] = max(1,0) = 1

• leftMax[3] = max(1,2) = 2

• leftMax[4] = max(2,1) = 2

也就是说，leftMax[i] 帮我们提前记录了当前位置左边最高的“挡板”。

3. rightMax 数组又表示什么？

int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}

这里的 rightMax[i] 表示：

从右边走到当前位置 i 为止，见过的最高柱子。

同样拿上面的例子：

height = [0,1,0,2,1]

则：

rightMax = [2,2,2,2,1]

解释一下：

• rightMax[4] = 1

• rightMax[3] = max(1,2) = 2

• rightMax[2] = max(2,0) = 2

• rightMax[1] = max(2,1) = 2

• rightMax[0] = max(2,0) = 2

于是现在对于任意位置，我们都能在 O(1) 时间知道：

• 左边最高墙是多少

• 右边最高墙是多少

4. 为什么当前位置能接的水量是这个公式？

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

这是整道题最核心的公式。

我们前面已经说过，当前位置水位上限取决于左右两边较矮的那堵墙。

所以当前位置最高能蓄到的水位就是：

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

但当前位置本身已经有一个柱子，高度是 height[i]。 所以真正可以装水的部分，就是上面的那一截：

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

例如：

• 左边最高是 3

• 右边最高是 4

• 当前柱子高度是 1

那么水位上限只能到 3，所以当前位置能接的水量是：

3 - 1 = 2

手动模拟一遍

我们用经典样例：

height = [0,1,0,2,1,0,1,3,2,1,2,1]

来简单走一下。

第一步：求 leftMax

得到：

leftMax = [0,1,1,2,2,2,2,3,3,3,3,3]

第二步：求 rightMax

得到：

rightMax = [3,3,3,3,3,3,3,3,2,2,2,1]

第三步：逐个位置算水量

比如：

下标 2

• height[2] = 0

• leftMax[2] = 1

• rightMax[2] = 3

可接水量：

min(1,3) - 0 = 1

下标 4

• height[4] = 1

• leftMax[4] = 2

• rightMax[4] = 3

可接水量：

min(2,3) - 1 = 1

下标 5

• height[5] = 0

• leftMax[5] = 2

• rightMax[5] = 3

可接水量：

min(2,3) - 0 = 2

下标 6

• height[6] = 1

• leftMax[6] = 2

• rightMax[6] = 3

可接水量：

min(2,3) - 1 = 1

继续把所有位置加起来，最终总和就是：

6

这正好是题目答案。

为什么这个方法是正确的？

因为每个位置是否能接水，本质上只由三件事决定：

1. 当前位置柱子高度

2. 左边最高柱子

3. 右边最高柱子

而左右最大值一旦提前算好，当前位置的雨水量就可以准确算出来。

为什么取左右最大值中的较小者？

因为水位会先从较低的那边溢出去。 所以不管另一边再高，真正限制水位的始终是“短板”。

这和“盛最多水的容器”那道题很像，本质上都是短板思想。

因此：

当前位置水位 = min(leftMax[i], rightMax[i])

这个结论是完全正确的。

复杂度分析

时间复杂度

代码一共做了三次线性扫描：

1. 一次计算 leftMax

2. 一次计算 rightMax

3. 一次统计总雨水

所以总时间复杂度是：

O(n)

空间复杂度

额外使用了两个长度为 n 的数组：

• leftMax

• rightMax

所以空间复杂度是：

O(n)

这道题真正想考什么？

这道题表面上是在算雨水，实际上考察的是两个很重要的能力。

第一，能不能把“局部结果”转化成“全局预处理”

如果你每次都临时去找左边最大值、右边最大值，当然能做，但效率太低。 真正高效的做法是：

把重复计算的中间信息提前存下来。

这就是动态规划/预处理数组的典型思想。

第二，能不能抓住短板原理

很多人第一次做这题时，容易误以为某个位置能装多少水只看一边就行。 其实一定要同时看左右两边，并且由较矮那边决定上限。

这就是整道题最核心的数学关系。

这题还有更优的写法吗？

有。

除了你现在这份“预处理左右最大值”的写法之外，这道题还可以用：

• 双指针

• 单调栈

来做。

其中双指针解法可以把空间复杂度进一步优化到：

O(1)

不过从理解角度来说，你这份代码非常适合作为入门写法。 因为它把整道题最核心的思路——“先求左右最大值，再算每个位置雨水量”——表达得特别清楚。

很多人第一次学这题，都是先把这个版本吃透，然后再去看双指针优化版。

总结

这道题的核心思想可以概括成一句话：

某个位置能接多少水，取决于它左边最高柱子和右边最高柱子中较矮的那个，再减去当前位置柱子的高度。

具体步骤就是：

1. 先预处理每个位置左边最高柱子 leftMax

2. 再预处理每个位置右边最高柱子 rightMax

3. 对每个位置计算：

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

4. 把所有位置的结果累加起来

这样就能在：

O(n)

的时间复杂度内解决问题。

这是一道非常经典、也非常值得反复理解的题。 因为它会让你真正体会到：

• 暴力扫描为什么慢

• 预处理数组为什么能优化

• “短板决定上限”这个规律到底怎么用

把这道题真正吃透之后，再去看：

• 盛最多水的容器

• 柱状图中最大的矩形

• 单调栈系列题目

• 双指针优化题

你会更容易抓住它们背后的共同思路。

因为“接雨水”本身就是数组规律题里非常经典的一道代表题。