27.LeetCode刷题之路42题接雨水

2020年6月11日14:58:43算法 LeetCode评论56阅读模式

题目链接

https://leetcode-cn.com/problems/trapping-rain-water/文章源自随机的未知-https://sjdwz.com/11134.html

题目内容

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
27.LeetCode刷题之路42题接雨水
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6文章源自随机的未知-https://sjdwz.com/11134.html

思路

我们可以设置两个数组,left_height_arrayright_height_array;
其中left_height_array表示当前柱子前面的所有柱子的最高值(不包括当前柱子);
right_height_array表示当前柱子后面的所有柱子的最高值(不包括当前柱子);
取left_height_array[i]与right_height_array[i]两个值的最小值,如果相等则取这个相同的值,存储在res数组中
在height[i]处可以存的水量的求法:
如果res[i]的值比height[i]大,当前凹处可以存res[i] - height[i]的水;
如果res[i]的值不比height[i]大,不能存水;
再把res[i]累加便可以得到最终存水量。
(其实可以在比较left_height_array[i]right_height_array[i] 大小关系时就可以进行累加存水量了。)文章源自随机的未知-https://sjdwz.com/11134.html

案例分析

height : [0,1,0,2,1,0,1,3,2,1,2,1]
先求解 left_height_array[i] 从前往后算:
第一个元素左边没有元素,所以left_height_array[0] = 0;
第二个元素左边元素有0,左边最高的是0,所以left_height_array[1] = 0;
第三个元素左边元素有0,1,左边最高的是1,所以left_height_array[2] = 1;
第四个元素左边元素有0,1,0,左边最高的是1,所以left_height_array[3] = 1;
第五个元素左边元素有0,1,0,2,左边最高的是2,所以left_height_array[4] = 2;
第六个元素左边元素有0,1,0,2,1左边最高的是2,所以left_height_array[5] = 2;
第七个元素左边元素有0,1,0,2,1,0,左边最高的是2,所以left_height_array[6] = 2;
第八个元素左边元素有0,1,0,2,1,0,1左边最高的是2,所以left_height_array[7] = 2;
第九个元素左边元素有0,1,0,2,1,0,1,3左边最高的是3,所以left_height_array[8] = 3;
第十个元素左边元素有0,1,0,2,1,0,1,3,2左边最高的是3,所以left_height_array[9] = 3;
第十一个元素左边元素有0,1,0,2,1,0,1,3,2,1左边最高的是3,所以left_height_array[10] = 3;
第十二个元素左边元素有0,1,0,2,1,0,1,3,2,1,2左边最高的是3,所以left_height_array[11] = 3;文章源自随机的未知-https://sjdwz.com/11134.html

所以left_height_array数组为
0,0,1,1,2,2,2,2,3,3,3,3
同理可求得right_height_array数组为
3,3,3,3,3,3,3,2,2,2,1,0;
height数组为:
0,1,0,2,1,0,1,3,2,1,2,1
index=0时,left_height_array[0] = 0,right_height_array[0] = 0不能放水,存水量为0;
index=1时,left_height_array[1] = 0,right_height_array[1] = 3不能放水,两者最小为0,存水量为0;
index=2时,left_height_array[2] = 1,right_height_array[1] = 3不能放水,两者最小为2,而height[i]为0,存水量为两者最小值 - height[i] = 1;
以此类推;
最后把它们都相加即可。文章源自随机的未知-https://sjdwz.com/11134.html

代码

class Solution {
    public int trap(int[] height) {
        int result = 0;
        if(height.length == 0return result;
        int[] left_height_array = new int[height.length];
        int[] right_height_array = new int[height.length];
        int left_max = 0;
        int right_max = 0;
        left_height_array[0] = 0;
        right_height_array[0] = 0;
        for(int i = 1;i<height.length;i++){
            if(height[i-1]>left_max){
                left_max = height[i-1];
            }
            left_height_array[i] = left_max;
        }

        for(int i = height.length -2;i>=0;i--){
            if(height[i+1]>right_max){
                right_max = height[i+1];
            }
            right_height_array[i] = right_max;
        }
        for(int i=0;i<height.length;i++){
            if(left_height_array[i] == right_height_array[i]){
                if(left_height_array[i] > height[i])
                    result+=left_height_array[i]-height[i];

            }else if(left_height_array[i] < right_height_array[i]){
                if(left_height_array[i] > height[i])
                    result+=left_height_array[i]-height[i];
            }else{
                if(right_height_array[i]>height[i])
                    result += right_height_array[i] - height[i];
            }
        }
        return result;
    }
}

欢迎关注

扫下方二维码即可关注,微信公众号:随机的未知
27.LeetCode刷题之路42题接雨水文章源自随机的未知-https://sjdwz.com/11134.html

文章源自随机的未知-https://sjdwz.com/11134.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年6月11日14:58:43
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11134.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
算法

详解归并排序

基本思想 归并排序的基本思想是: 先将序列一次次分成子序列,直到子序列长度为1; 再将已有序的子序列合并,得到完全有序的序列。 可以看出归并排序运用了 分而治之的思想 。 例子 输入数组 < 2, 5...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定