专栏首页code随笔的专栏Leetcode 42题 接雨水(Trapping Rain Water)

Leetcode 42题 接雨水(Trapping Rain Water)

题目链接

https://leetcode-cn.com/problems/trapping-rain-water/

题目内容

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

示例图

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

思路

我们可以设置两个数组,「left_height_array」「right_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]」 大小关系时就可以进行累加存水量了。)

案例分析

「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;

所以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; 以此类推; 最后把它们都相加即可。

代码

class Solution {
    public int trap(int[] height) {
        int result = 0;
        if(height.length == 0) return 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;
    }
}

本文分享自微信公众号 - code随笔(yzsgxhywh),作者:灿烂星空StarrySky

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 详解冒泡排序算法

    冒泡排序的基本思想是: 通过对待排序的序列从前向后依次比较相邻元素的值,如果发现逆序则交换。 逆序的含义:如果想把序列从小到大排序,那么两个数中前面的...

    code随笔
  • Java中的基本数据类型和包装类型的这些知识,你都知道吗?

    Java 中的基本数据按类型可以分为四大类:布尔型、整数型、浮点型、字符型; 这四大类包含 8 种基本数据类型。

    code随笔
  • 希尔排序算法

    当待插入元素是一个很小(当需求是从小到大排序时,从大到小排序时此处为很大)直接插入排序需要移动较多次数,性能会很差。希尔排序解决了这一问题。

    code随笔
  • 【每天一道编程系列-2018.2.28】(Ans)

      Given n non-negative integers a1, a2, …, an, where each represents a point at...

    yesr
  • 【LeetCode-011】Container With Most Water

    Given n non-negative integers a1, a2, ..., an , where each represents a point at...

    周三不加班
  • 每日两题 T15

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

    合一大师
  • 地平线机器人杨铭:深度神经网络在图像识别应用中的演化

    机器之心整理 编辑:杜雪 4 月 15 日,杨铭博士在机器之心线下活动 Interface 上做了一次题为「深度神经网络在图像识别应用中的演化」的演讲。这篇文章...

    机器之心
  • Python练手例子(12)

    69、有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。

    py3study
  • 根据端口号查找服务,根据进程查找端口,查找开放的所有端口

    醉生萌死
  • 深度学习三人行(第12期)----CNN经典网络之ResNet

    接下来我们一起学习下关于CNN中的另一个比较经典的网络ResNet的相关知识,学习的路上我们多多交流,共同进步。本期主要内容如下:

    智能算法

扫码关注云+社区

领取腾讯云代金券