LeetCode 42. 接雨水：从按列计算到前后缀最大值，彻底讲透为什么这一列能接多少水

摘要

LeetCode 42. 接雨水（Trapping Rain Water） 是数组题中的经典难题，也是面试中高频出现的问题之一。很多人第一次看到这道题时，会先从“整个图形能装多少水”去思考，但真正高效、稳定、容易写对的方法，往往来自一个关键转换：

不去直接算整个区域，而是去计算每一根柱子上方能接多少水，然后累加。

而要算出每一列能接多少水，就必须知道：

• 它左边最高的柱子有多高
• 它右边最高的柱子有多高

这篇文章将围绕这个核心思路展开，系统讲清楚：

• 为什么按列计算是正确的
• 为什么每列雨水高度等于 min(左侧最高, 右侧最高) - 当前高度
• 为什么这个值在定义正确时其实不会为负
• 如何用两个数组预处理左右最大值
• 如何写出稳定、清晰、面试友好的 Java 代码

如果真正理解了这篇文章，那么这道题就不再只是“背模板”，而会变成一道非常标准的前缀/后缀预处理题。

---

目录

---

一、题目描述

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

示例：

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

---

二、这道题真正难在哪里

这道题的难点不在代码本身，而在于：

1. 如何建立正确的计算视角

很多人会本能地想从整体图形面积出发，但这种方式很难直接落地。
真正更自然的视角是：

按列计算每个位置上方能接多少水。

2. 如何确定某一列上方的水位

一根柱子上方能不能存水，不只取决于它自己，还取决于它左右两边是否有更高的“挡板”。

3. 如何把朴素思路优化成线性时间

如果对每个位置都向左、向右扫描一次去找最大值，虽然能做出来，但复杂度会偏高。
更优的方法是提前把“左侧最高”和“右侧最高”都预处理出来。

---

三、核心思路：把总雨水拆成“每一列的雨水”

这是整道题最重要的思想转换。

设当前位置为 i，柱子高度为：

height[i]

如果问：第 i 列上方最多能接多少水？

那么答案取决于两边挡板的高度：

• 左边最高柱子：leftMax[i]
• 右边最高柱子：rightMax[i]

当前位置能形成的水位高度，是由左右两边较低的挡板决定的，也就是：

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

然后再减去当前柱子本身的高度：

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

最后把所有位置的 water[i] 累加起来，就是总雨水量。

---

四、为什么是 min(左侧最高, 右侧最高) 而不是 max(...)

这个问题非常关键。

假设某一列：

• 左边最高柱子是 5
• 右边最高柱子是 3

那么这一列的水位最多只能到 3，而不可能到 5。
原因很简单：

水会从更矮的那一边流出去。

所以真正限制水位高度的，不是更高的挡板，而是更矮的挡板。

因此该列的有效水位只能取：

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

这就是整道题最核心的物理直觉。

---

五、先从朴素想法出发：每个位置都现找左右最大值

最朴素的写法是：

• 枚举每个位置 i
• 向左扫描，找出 0..i 中的最大高度
• 向右扫描，找出 i..n-1 中的最大高度
• 计算当前位置能接的雨水
• 累加

这个思路完全正确，但问题在于：

• 每个位置都要向左扫一遍
• 每个位置都要向右扫一遍

于是总复杂度会达到 O(n^2)。

这就提示我们：

能不能把“每个位置左边最高是多少”和“每个位置右边最高是多少”提前算出来？

答案当然可以。

---

六、前后缀最大值数组：把重复计算提前做掉

这道题的标准解法之一，就是预处理两个数组：

1. left[i]

表示：

从左到右看，到位置 i 为止，出现过的最高柱子高度

也就是：

left[i] = max(height[0], height[1], ..., height[i])

2. right[i]

表示：

从右到左看，到位置 i 为止，出现过的最高柱子高度

也就是：

right[i] = max(height[i], height[i+1], ..., height[n-1])

这样一来，对于任意位置 i：

water[i] = min(left[i], right[i]) - height[i]

就能在 O(1) 时间内直接得到。

最后遍历一遍累加即可。

---

七、代码逐行精注释版

下面先给出一版在原思路基础上整理后的、适合讲解与面试的实现，并加入完整注释。

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

        // 边界处理：
        // 少于 3 根柱子，不可能形成凹槽，也就无法接雨水
        if (n < 3) return 0;

        // left[i] 表示：从左到右到达 i 位置时，左侧（含自己）最高的柱子高度
        int[] left = new int[n];

        // right[i] 表示：从右到左到达 i 位置时，右侧（含自己）最高的柱子高度
        int[] right = new int[n];

        // 初始化边界
        left[0] = height[0];
        right[n - 1] = height[n - 1];

        int sum = 0;

        // 预处理 left 数组
        // left[i] = max(left[i - 1], height[i])
        // 含义：当前位置左侧最高的柱子，
        // 要么是前一个位置的左侧最高柱子，
        // 要么就是当前位置自己
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }

        // 预处理 right 数组
        // right[i] = max(right[i + 1], height[i])
        // 含义：当前位置右侧最高的柱子，
        // 要么是后一个位置的右侧最高柱子，
        // 要么就是当前位置自己
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }

        // 计算每一列能接多少水
        // 首尾两根柱子无法存水，因此从 1 到 n - 2 即可
        for (int i = 1; i < n - 1; i++) {
            // 当前列能达到的最高水位，由左右两边较矮的挡板决定
            int waterLevel = Math.min(left[i], right[i]);

            // 当前列可接的雨水 = 水位高度 - 柱子本身高度
            int water = waterLevel - height[i];

            // 在本题这种定义下，water 理论上不会为负
            // 因为 left[i] >= height[i] 且 right[i] >= height[i]
            // 所以 min(left[i], right[i]) >= height[i]
            // 这里直接累加即可
            sum += water;
        }

        return sum;
    }
}

---

八、原始代码逐行详细注释版（看这个就行，leetcode能全过，自己写的）

下面保留原有写法风格，对代码进行详细注释，便于逐句理解。

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

        // left[i]：表示位置 i 左边（含自己）最高的柱子高度
        int[] left = new int[n];

        // right[i]：表示位置 i 右边（含自己）最高的柱子高度
        int[] right = new int[n];

        // 初始化：
        // 最左边位置的左侧最高值只能是自己
        left[0] = height[0];

        // 最右边位置的右侧最高值只能是自己
        right[n - 1] = height[n - 1];

        // 用于记录总雨水量
        int sum = 0;

        // 从左往右构造 left 数组
        // left[i] 等于：
        // 1. 前一个位置已经记录好的左侧最高值 left[i - 1]
        // 2. 当前柱子高度 height[i]
        // 两者中的较大值
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }

        // 从右往左构造 right 数组
        // right[i] 等于：
        // 1. 后一个位置已经记录好的右侧最高值 right[i + 1]
        // 2. 当前柱子高度 height[i]
        // 两者中的较大值
        for (int i = n - 2; i > 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }

        // 遍历中间位置，统计每一列能接的雨水
        // 注意：最左边和最右边无法接雨水，所以从 1 到 n - 2
        for (int i = 1; i < n - 1; i++) {

            // 当前位置能达到的有效水位，取决于左右较矮的一侧
            int waterLevel = Math.min(left[i], right[i]);

            // 当前列雨水量 = 有效水位 - 当前柱子高度
            int water = waterLevel - height[i];

            // 为防止出现负数，代码中做了 > 0 判断
            // 但如果 left 和 right 的定义正确，
            // 那么这里其实理论上不会小于 0
            if (water > 0) {
                sum += water;
            }
        }

        return sum;
    }
}

---

九、为什么这里“减去本柱子高度”不会减成负数

这是这道题非常值得讲清楚的一个细节。

代码中写了：

if ((Math.min(left[i], right[i]) - height[i]) > 0) {
    sum += Math.min(left[i], right[i]) - height[i];
}

很多人会想：是不是一定要这样防一下，避免减成负数？

严格来说，如果 left 和 right 的定义正确，这里其实不会出现负数。

因为：

对 left[i]

它表示位置 i 左边（含自己）最高的柱子高度，所以一定满足：

left[i] >= height[i]

对 right[i]

它表示位置 i 右边（含自己）最高的柱子高度，所以一定满足：

right[i] >= height[i]

因此：

min(left[i], right[i]) >= height[i]

于是：

min(left[i], right[i]) - height[i] >= 0

也就是说，在定义正确时，当前位置接水量理论上不可能是负数。

---

十、那为什么代码里还写 > 0 判断

这层判断并不是错误，它属于一种防御式写法。

它的作用是：

• 让代码语义更直观
• 即便某些数组没有正确初始化，也不至于把负值加进结果

但从算法原理上说，如果前缀/后缀最大值数组构造正确，那么这一层判断可以省略，直接累加即可。

例如可以写成：

sum += Math.min(left[i], right[i]) - height[i];

这在逻辑上依然成立。

---

十一、代码中的一个小边界细节

原代码中 right 数组的构造循环写成：

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

这意味着：

• right[n - 1] 已初始化
• right[n - 2] 到 right[1] 会被正确赋值
• 但 right[0] 不会被赋值

这在当前代码里不会出错，因为后面计算雨水时遍历的是：

for (int i = 1; i < n - 1; i++)

根本不会使用 right[0]。

所以这份代码是能正确工作的。

不过从“数组定义完整性”的角度看，更推荐写成：

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

这样整个 right 数组会被完整填满，语义也更统一。

---

十二、为什么首尾两列一定接不到水

代码里遍历求和时写的是：

for (int i = 1; i < n - 1; i++)

而不是从 0 到 n - 1。

这是因为：

最左边一列

左边没有柱子，无法形成左挡板，所以接不到水。

最右边一列

右边没有柱子，无法形成右挡板，所以接不到水。

接雨水的前提，是当前位置两边都得有挡板。
因此首尾位置一定不可能接水。

---

十三、用一个经典例子完整走一遍

以题目经典示例：

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

为例。

1. 构造 left 数组

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

含义是：到当前位置为止，从左边看见过的最高柱子高度。

2. 构造 right 数组

right = [3,3,3,3,3,3,3,3,2,2,2,1]

含义是：从当前位置往右看，能见过的最高柱子高度。

3. 按列计算雨水

例如位置 2：

height[2] = 0
left[2] = 1
right[2] = 3

所以：

water[2] = min(1, 3) - 0 = 1

位置 5：

height[5] = 0
left[5] = 2
right[5] = 3

所以：

water[5] = min(2, 3) - 0 = 2

把所有位置累加起来，最终结果就是 6。

---

十四、这道题本质上是一道“按列求贡献”的题

这道题特别值得总结的地方在于，它训练的是一种非常重要的算法思维：

不要总想着直接求整体结果，而是尝试把整体拆成每个位置的局部贡献，再做累加。

在这道题中：

• 总雨水量 = 每一列的雨水量之和
• 每一列的雨水量 = 有效水位 - 当前柱高
• 有效水位 = 左右挡板较矮者

一旦这个分解视角建立起来，整道题就清晰很多。

---

十五、复杂度分析

时间复杂度

代码总共做了三次线性遍历：

1. 构造 left
2. 构造 right
3. 统计总雨水

所以总时间复杂度是：

O(n)

空间复杂度

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

• left
• right

所以空间复杂度是：

O(n)

---

十六、推荐的面试写法

下面给出一版更完整、更适合面试与正式提交的实现：

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

        // 少于 3 根柱子无法接水
        if (n < 3) return 0;

        int[] left = new int[n];
        int[] right = new int[n];

        left[0] = height[0];
        right[n - 1] = height[n - 1];

        // 构造 left 数组
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }

        // 构造 right 数组
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }

        int sum = 0;

        // 累加每一列的雨水
        for (int i = 1; i < n - 1; i++) {
            sum += Math.min(left[i], right[i]) - height[i];
        }

        return sum;
    }
}

这版代码的特点是：

• 边界清晰
• 数组定义完整
• 逻辑严谨
• 面试时也比较容易解释

---

十七、面试高频追问总结

1. 为什么一列能接多少水，由左右最高柱子的较小值决定

因为水会从较矮的一边流出去，所以最终能形成的水位，最多只能达到左右挡板中较低的那一侧。

---

2. 为什么要减去当前柱子高度

因为 min(left[i], right[i]) 表示的是当前位置能达到的总水位高度，而当前位置本身已经有一根柱子占据了 height[i] 的空间，所以真正能装水的部分必须减掉柱子本身。

---

3. 为什么不会减成负数

因为：

left[i] >= height[i]
right[i] >= height[i]

因此：

min(left[i], right[i]) >= height[i]

所以结果不会小于 0。

---

4. 为什么首尾位置不用计算

因为最左边没有左挡板，最右边没有右挡板，两端都不可能蓄水。

---

5. 这道题还能继续优化吗

可以。
当前解法时间复杂度已经是 O(n)，但空间复杂度是 O(n)。
进一步还可以优化成：

• 双指针解法：O(n) 时间，O(1) 空间
• 单调栈解法：也是经典做法

不过从“好理解、好讲清楚、好面试”角度来看，前后缀最大值解法是非常优秀的入门标准解。

---

十八、和双指针解法相比，这种方法的优势是什么

虽然双指针法空间更优，但当前这种前后缀最大值方法有几个明显优势：

1. 思路非常直观

直接对应“每列雨水 = 左右挡板较小者 - 当前高度”。

2. 代码结构清晰

分三步走：

• 预处理左最大值
• 预处理右最大值
• 统计答案

3. 不容易写错

相比双指针，前后缀法的状态变化更少，更适合第一次掌握这道题。

因此，如果是为了写博客、讲思路、做教学，这种方法非常合适。

---

十九、整道题的学习路线总结

真正掌握 LeetCode 42. 接雨水，建议按这个顺序理解：

第一步：先建立“按列求贡献”的视角

总雨水量，不是直接求整体面积，而是求每一列的雨水再累加。

第二步：理解单列雨水公式

当前位置雨水量：

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

第三步：意识到左右最大值会被重复查询

于是使用两个数组进行预处理。

第四步：完成线性遍历统计

每个位置 O(1) 求贡献，总体 O(n)。

---

二十、结语

LeetCode 42. 接雨水 是一道非常经典的数组题，它之所以经典，不只是因为难度适中，更因为它特别能训练一种重要的算法思维：

当一个整体问题看起来难以下手时，尝试把它拆成“每个位置的局部贡献”，再统一累加。

在这道题中：

• 整体雨水量被拆成了每一列的雨水量
• 每一列雨水量又被分解为“左右挡板的较小值减去自身高度”
• 再借助前后缀最大值数组，把原本重复的查询优化成线性时间

把这条思路真正学透之后，不只是这道题，很多“按位置求贡献”的数组题都会变得清晰很多。

---