leetcode42-接雨水

原题

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

leetcode42-接雨水

上面是由数组 [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

解法

思想

每一列能存下的雨水单位等于左右最高两列当中的较矮一列与当前高度的高度差

leetcode42-接雨水

如图,第五列的积雨水量,等于左边最高一列(第四列left)和右边最高一列(第八列right)的较矮一列(left)与当前列高度的高度差(2-1=1)

如果两边有一边没有比当前列高的列,则当前列不会积水。

代码

我一开始是这样写的:

class Solution {
    public int trap(int[] height) {
        int total = 0;
        int count = height.length;
        Integer[] left = new Integer[count];
        Integer[] right = new Integer[count];
        for(int i = 0;i<count;i++){
            for(int j = 1;j<=i;j++){//更新左边所有列的right
                if(right[j]==null||height[i]>right[j]) right[j] = height[i];
            }
            for(int j = i;j<count-1;j++){//更新右边所有列的left
                if(left[j]==null||height[i]>left[j]) left[j] = height[i];
            }
        }
        for(int i = 0;i<count;i++){
            if(left[i]==null || right[i] == null) continue;
            total += (Math.min(left[i],right[i])-height[i]);
        }
        return total;
    }
}

时间复杂度达到了N2级别,那么如何优化呢?

  1. 不必使用null来表示没有比当前列高的列,即使两列相等,高度差也是0,相当于不积水。
  2. 利用动态规划的思想,如果前一列的left比当前列高,则当前列的left也等于前一列的left。对于right也是一样的。

优化后:

class Solution {
    public int trap(int[] height) {
        int total = 0;
        int count = height.length;
        if(count==0) return 0;
        Integer[] left = new Integer[count];
        Integer[] right = new Integer[count];
        left[0] = height[0];
        right[count-1] = height[count-1];
        for(int i = 1;i<count;i++){//从左向右更新left
            if(height[i]>left[i-1]) left[i] = height[i];
            else left[i] = left[i-1];
        }
        for(int i = count-2;i>=0;i--){//从右向左更新right
            if(height[i]>right[i+1]) right[i] = height[i];
            else right[i] = right[i+1];
        }
        for(int i = 0;i<count;i++){
            total += (Math.min(left[i],right[i])-height[i]);
        }
        return total;
    }
}
func trap(height []int) int {
    lmax := make([]int, len(height))
    rmax := make([]int, len(height))
    for i := 0; i < len(height) - 1; i++{
        lmax[i+1] = max(height[i], lmax[i])
    }
    for i := len(height) -1; i > 0; i--{
        rmax[i-1] = max(height[i], rmax[i])
    }
    sum := 0
    for i := 0; i < len(height); i++{
        long := min(lmax[i], rmax[i]) - height[i]
        if long > 0{
            sum += long
        }
    }
    return sum
}   

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode42-%e6%8e%a5%e9%9b%a8%e6%b0%b4/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月22日
下一篇 2020年1月23日

相关推荐

  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0110
  • leetcode131-分割回文串

    原题 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], …

    算法 2020年5月22日
    0100
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0700
  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190
  • leetcode39-组合总和

    原题 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates …

    2020年5月1日
    02720
  • leetcode206-反转链表

    原题 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法…

    2019年12月16日
    0150
  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02870
  • leetcode1248-统计「优美子数组」

    原题 给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。 …

    算法 2020年4月21日
    0320
  • leetcode376-摆动序列

    原题 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,…

    算法 2020年2月18日
    0110

发表回复

登录后才能评论