42. 接雨水

二哥瞎逼逼：接雨水是一道非常经典的 LeetCode 题，在不少笔试中见到过，所

以大家最好都要掌握。

题意

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

能接多少雨水。

难度

困难

示例 1

042.接雨水-20240807155502.png

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

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单

位的雨水（蓝色部分表示雨水）。

示例 2

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

输出：9

分析

虽然这道题是 hard，但不要怕，我们可以抽丝剥茧将重要的信息剥离出来，一步一步解

决它。

一个 能接雨水的容器 肯定是由 左边界、右边界和底边构成的。

换句话说，每一根柱子 i 用来做为底边的时候，它能接多少雨水，取决于左边界和右边界

的最小值。

042.接雨水-20240807163418.png

这个点如果想通了，这道题就不再是一道困难题，而是简单题了。

我们直接用暴力来解。循环遍历每一根柱子，然后再找到左边最高的，和右边最高的，然

后取两者的最小值减去当前柱子的高度，就是当前柱子能接到的雨水量。

class Solution {

public int trap(int[] height) {

int n = height.length;

int totalWater = 0;

for (int i = 0; i < n; i++) {

int leftMax = 0, rightMax = 0;

// 找到左边最高的柱子

for (int j = 0; j <= i; j++) {

leftMax = Math.max(leftMax, height[j]);

}

// 找到右边最高的柱子

for (int j = i; j < n; j++) {

rightMax = Math.max(rightMax, height[j]);

}

// 当前柱子能接的雨水量

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

}

return totalWater;

}

public static void main(String[] args) {

Solution solution = new Solution();

int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

System.out.println("能接的雨水量: " + solution.trap(height)); // 输出 6

 }

}

题解很好理解，第一层 for 循环遍历每一根柱子，第二层的两个 for 循环分别找到左边最

高的柱子和右边最高的柱子，当前柱子能够接到的雨水就等于左右最高柱子的最小值减去

当前柱子的高度。

比如示例 1 中的第一根柱子高度为 0，左边最高的柱子是 0，右边最高的柱子是 3，第一

根柱子能接到的雨水就是 0。

第二根柱子高度为 1，左边最高的柱子是 0，右边最高的柱子是 3，第二根柱子能接到的

雨水就是 0。

第三根柱子高度为 0，左边最高的柱子是 1，右边最高的柱子是 3，第三根柱子能接到的

雨水就是 1。

但是很遗憾，这个解法直接超出时间限制了，因为每根柱子都要前后遍历一次去找左右最

高的柱子，效率太低了。

042.接雨水-20240807162144.png

分析 2

为了优化暴力算法，我们可以预先计算每根柱子的左侧最高柱子和右侧最高柱子，然后再

一次遍历计算每个柱子能接的雨水量。

说白了，就是把暴力算法中内层的两个 for 循环拆出来放到外层，用两个数组来记录当前

柱子左边和右边最低和最高的柱子，空间换时间，这样时间效率就会有大幅度的提升。

class Solution {

public int trap(int[] height) {

int n = height.length;

if (n == 0) return 0;

// 预先计算每个柱子的左侧最高柱子高度

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]);

 }

// 预先计算每个柱子的右侧最高柱子高度

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;

}

public static void main(String[] args) {

Solution solution = new Solution();

int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

System.out.println("能接的雨水量: " + solution.trap(height)); // 输出 6

}

}

来看一下现在的时间效率，果然提升不少：

042.接雨水-20240807164020.png

总结

这道题的关键点在于理解 能接雨水的容器 是由什么条件决定的，一旦想清楚这个，就很

容易想到解法了。

其实工作当中也是这样，怎么把复杂的需求抽象化，抽象成代码可以去实现的逻辑，然后

很多看似困难的问题就迎刃而解了。

这道题本身对技术层面的考察就还是 for 循环和数组，别的也就没有了。

力扣链接：https://leetcode.cn/problems/trapping-rain-water/