Java 版 LeetCode 刷题笔记：042.接雨水

作者：沉默王二
发布时间：2022-09-19T21:51:17.229+0800

---

042.接雨水

题意

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

难度

困难

示例

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

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

分析

本题为困难程度，但不要怕，我们可以抽丝剥茧的将重要的信息剥离出来，一步一步解决它。

想一想，能接到雨水，那么一个 能接雨水的区域 肯定是由 左边界、右边界和底来构成的。我们要做的就是快速找到这三个元素。

假如我们现在到了i这个位置，那么如果它能够作为底层的话，它的左边和右边肯定都是比它高的。

也就是说，如果这个点能够作为底层，那么它 这一列 能够接的雨水，就是由它左右边界的最小值来确定的。

而它的边界——不就是左边的最大值和右边的最大值吗？

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

我们来回顾一遍整个算法的过程：

• 将 “雨水” 分成一列一列来计算
• 该列能累计的 “雨水” 由maxLef[i]和maxRig[i]的最小值来决定——即min(maxLef[i],maxRig[i]) - height[i]，如果左右两边的最小值比该列的高度小，则说明该列不能接雨水，直接跳过。

这样子我们就能够轻轻松松的解决这道困难题了。

class Solution {

        int ans = 0;        int rigMax[] = new int[height.length];        int maxx = 0;        for(int i = height.length - 1;i >= 0;i--){            rigMax[i] = maxx;            maxx = Math.max(maxx,height[i]);        }        maxx = 0;        int lefMax[] = new int[height.length];        for(int i = 0;i < height.length;i++){            lefMax[i] = maxx;            maxx = Math.max(maxx,height[i]);        }        for(int i = 0;i < height.length;i++)            ans += Math.max(Math.min(lefMax[i],rigMax[i]) - height[i],0);        return ans;    }}

时间复杂度：，因为我们只是将整个数组遍历了三遍。

而且效率也非常不错。

总结

本题我们将接雨水的容器拆分成一列一列来计算，联系一下现实生活，也不难得出结论，一个水塘的能够蓄水的高度其实就是水面到水塘底的距离，最大容量是由两边的最低高度确定的。所以本题虽然是 hard 模式，但不用想得太复杂，仔细分析以下，就可以得出破题之法。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 810 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

042.接雨水

题意

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

难度

困难

示例

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

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

分析

本题为困难程度，但不要怕，我们可以抽丝剥茧的将重要的信息剥离出来，一步一步解决它。

想一想，能接到雨水，那么一个 能接雨水的区域 肯定是由 左边界、右边界和底来构成的。我们要做的就是快速找到这三个元素。

假如我们现在到了i这个位置，那么如果它能够作为底层的话，它的左边和右边肯定都是比它高的。

也就是说，如果这个点能够作为底层，那么它 这一列 能够接的雨水，就是由它左右边界的最小值来确定的。

而它的边界——不就是左边的最大值和右边的最大值吗？

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

我们来回顾一遍整个算法的过程：

• 将 “雨水” 分成一列一列来计算
• 该列能累计的 “雨水” 由maxLef[i]和maxRig[i]的最小值来决定——即min(maxLef[i],maxRig[i]) - height[i]，如果左右两边的最小值比该列的高度小，则说明该列不能接雨水，直接跳过。

这样子我们就能够轻轻松松的解决这道困难题了。

class Solution {

        int ans = 0;        int rigMax[] = new int[height.length];        int maxx = 0;        for(int i = height.length - 1;i >= 0;i--){            rigMax[i] = maxx;            maxx = Math.max(maxx,height[i]);        }        maxx = 0;        int lefMax[] = new int[height.length];        for(int i = 0;i < height.length;i++){            lefMax[i] = maxx;            maxx = Math.max(maxx,height[i]);        }        for(int i = 0;i < height.length;i++)            ans += Math.max(Math.min(lefMax[i],rigMax[i]) - height[i],0);        return ans;    }}

时间复杂度：，因为我们只是将整个数组遍历了三遍。

而且效率也非常不错。

总结

本题我们将接雨水的容器拆分成一列一列来计算，联系一下现实生活，也不难得出结论，一个水塘的能够蓄水的高度其实就是水面到水塘底的距离，最大容量是由两边的最低高度确定的。所以本题虽然是 hard 模式，但不用想得太复杂，仔细分析以下，就可以得出破题之法。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 810 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

042.接雨水

题意

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

难度

困难

示例

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

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

分析

本题为困难程度，但不要怕，我们可以抽丝剥茧的将重要的信息剥离出来，一步一步解决它。

想一想，能接到雨水，那么一个 能接雨水的区域 肯定是由 左边界、右边界和底来构成的。我们要做的就是快速找到这三个元素。

假如我们现在到了i这个位置，那么如果它能够作为底层的话，它的左边和右边肯定都是比它高的。

也就是说，如果这个点能够作为底层，那么它 这一列 能够接的雨水，就是由它左右边界的最小值来确定的。

而它的边界——不就是左边的最大值和右边的最大值吗？

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

我们来回顾一遍整个算法的过程：

• 将 “雨水” 分成一列一列来计算
• 该列能累计的 “雨水” 由maxLef[i]和maxRig[i]的最小值来决定——即min(maxLef[i],maxRig[i]) - height[i]，如果左右两边的最小值比该列的高度小，则说明该列不能接雨水，直接跳过。

这样子我们就能够轻轻松松的解决这道困难题了。

class Solution {

        int ans = 0;        int rigMax[] = new int[height.length];        int maxx = 0;        for(int i = height.length - 1;i >= 0;i--){            rigMax[i] = maxx;            maxx = Math.max(maxx,height[i]);        }        maxx = 0;        int lefMax[] = new int[height.length];        for(int i = 0;i < height.length;i++){            lefMax[i] = maxx;            maxx = Math.max(maxx,height[i]);        }        for(int i = 0;i < height.length;i++)            ans += Math.max(Math.min(lefMax[i],rigMax[i]) - height[i],0);        return ans;    }}

时间复杂度：，因为我们只是将整个数组遍历了三遍。

而且效率也非常不错。

总结

本题我们将接雨水的容器拆分成一列一列来计算，联系一下现实生活，也不难得出结论，一个水塘的能够蓄水的高度其实就是水面到水塘底的距离，最大容量是由两边的最低高度确定的。所以本题虽然是 hard 模式，但不用想得太复杂，仔细分析以下，就可以得出破题之法。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 810 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412