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日

相关推荐

  • 剑指offer57-和为s的连续正数序列

    原题(来源Leetcode) 输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。 序列内的数字由小到大排列,不同序列按照首个数字从小到…

    算法 2020年3月6日
    060
  • leetcode104-二叉树的最大深度

    原题 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例:给定二叉树 [3,9,20,null…

    算法 2020年1月11日
    090
  • leetcode331-验证二叉树的前序序列化

    原题 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。 _9_ / \ 3 2…

    算法 2020年1月26日
    0100
  • leetcode72-编辑距离

    原题 给你两个单词 word1 和 word2 ,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字…

    2020年4月6日
    0140
  • leetcode198-打家劫舍

    原题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会…

    算法 2020年5月29日
    060
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    0100
  • leetcode209-长度最小的子数组

    原题 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = …

    算法 2019年11月20日
    0170
  • leetcode752-打开转盘锁

    原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由…

    2019年12月9日
    0290
  • leetcode203-移除链表元素

    原题 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5 解法 思想 pre指…

    算法 2019年12月16日
    0360
  • leetcode14-最长公共前缀

    原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “…

    算法 2019年11月18日
    0110

发表回复

登录后才能评论