给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入: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
这道题理解起来有点困难,解法也有很多,这里介绍一种我认为比较好理解的思路:每个元素能在结果中贡献多少个雨水呢?以上面的示例 1 为例,输入:
0,1,0,2,1,0,1,3,2,1,2,1
通过推断可以看到,列 i 对结果的贡献是:
max(min(left_max(i),right_max(i)) - heighti,0)
class Solution {
public int trap(int[] height) {
int[] left = new int[height.length];
int[] right = new int[height.length];
for(int i = 1; i < height.length - 1; i++) {
left[i] = Math.max(left[i - 1], height[i - 1]);
}
for(int i = height.length - 2; i >= 0; i--) {
right[i] = Math.max(right[i + 1], height[i + 1]);
}
// 遍历每个元素,分别找到左右第一个比它大的元素
int ans = 0;
for(int i = 1; i < height.length - 1; i++) {
int min = Math.min(left[i], right[i]);
if(min > height[i]) {
ans += min - height[i];
}
}
return ans;
}
}
项目 GitHub LeetCode 全解,欢迎大家 star、fork、merge,共同打造最全 LeetCode 题解!
Java 编程思想-最全思维导图-GitHub 下载链接,需要的小伙伴可以自取~!!!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。