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

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

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

相关推荐

  • leetcode1162-地图分析

    原题 你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域…

    2020年3月29日
    0150
  • leetcode18-四数之和

    原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 ta…

    算法 2020年5月5日
    0110
  • leetcode64-最小路径和

    原题 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明: 每次只能向下或者向右移动一步。 示例: 输入: [ [1,3…

    算法 2020年2月24日
    090
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0190
  • leetcode62-不同路径

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月21日
    0240
  • leetcode530-二叉搜索树的最小绝对差

    原题 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例: 输入:    1    &n…

    算法 2020年2月22日
    01320
  • leetcode4-寻找两个有序数组的中位数

    这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m…

    算法 2020年1月9日
    0620
  • leetcode112-路径总和

    原题 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:  给定如下二叉树,…

    算法 2020年1月12日
    0140
  • 蓝桥杯试题-翻硬币

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写…

    算法 2020年3月1日
    0140
  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100

发表回复

登录后才能评论