LeetCode42.接雨水
目录
题目描述
给定
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提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
方法一 动态规划
思路:
整体思路是一列一列的计算,把每一列的雨水加起来就是总的答案。
每一列如何计算呢?取左边的最大值和右边的最大值中较小的,就是雨水最高达到的高度,该高度-height[i]就是这一列雨水的量。若对于每一列,都向左向右找最大,那时间复杂度会达到 O(n^2)
这就用到动态规划,leftMax[i]表示i列及i列左侧的最高值,leftMax[i]=max(leftMax[i-1],height[i])。rightMax[i]表示i列及i列右侧的最高值,rightMax[i]=max(rightMax[i+1],height[i])
代码:
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 ans=0;
for(int i=0;i<n;i++){
ans+=Math.min(leftMax[i],rightMax[i])-height[i];
}
return ans;
}
}
参考链接:. - 力扣(LeetCode)
原文地址:https://blog.csdn.net/weixin_62438655/article/details/137826063
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!