首页 > 其他分享 >leetcode[42][hard]接雨水

leetcode[42][hard]接雨水

时间:2025-01-11 17:32:37浏览次数:8  
标签:leftMax rightMax int hard 42 height 数组 下标 leetcode

 目录

题目

思路

答案


一、题目

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

示例 1:

输入:height = [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 个单位的雨水(蓝色部分表示雨水)。 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

二、思路

思路:动态规划

对于下标 i,下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值,下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。

朴素的做法是对于数组 height 中的每个元素,分别向左和向右扫描并记录左边和右边的最大高度,然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n,该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度,因此总时间复杂度是 O(n2)。

上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度,则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法,可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。

创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤i<n,leftMax[i] 表示下标 i 左边的位置中,height 的最大高度,rightMax[i] 表示下标 i 右边的位置中,height 的最大高度。

显然,leftMax[0]=0,rightMax[n−1]=0。两个数组的其余元素的计算如下:

当 1≤i≤n−1 时,leftMax[i]=max(leftMax[i−1],height[i-1]);

当 0≤i≤n−2 时,rightMax[i]=max(rightMax[i+1],height[i+1])。

因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值,反向遍历数组 height 得到数组 rightMax 的每个元素值。

在得到数组 leftMax 和 rightMax 的每个元素值之后,对于 0≤i<n,下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。若为负数,则表示两边的柱子比height[i]低,不能储水。遍历每个下标位置即可得到能接的雨水总量。

三、答案

class Solution {
    public int trap(int[] height) {
        //leftMax[i]表示下标为i的柱子左边的最大高度
        int[] leftMax = new int[height.length];
        //rightMax[i]表示下标为i的柱子右边的最大高度
        int[] rightMax = new int[height.length];
        leftMax[0] = 0;
        rightMax[height.length - 1] = 0;
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
        }
        int total = 0;
        for (int i = 0; i < height.length; i++) {
            //下标为i的柱子的储水量=Math.min(leftMax[i], rightMax[i]) - height[i]。若为负数,则表示两边的柱子比height[i]低,不能储水
            if (Math.min(leftMax[i], rightMax[i]) - height[i] > 0) {
                total += Math.min(leftMax[i], rightMax[i]) - height[i];
            }
        }
        return total;
    }
}


日日刷算法,老年痴呆远离我~

标签:leftMax,rightMax,int,hard,42,height,数组,下标,leetcode
From: https://blog.csdn.net/lydia_cmy/article/details/145006982

相关文章

  • LeetCode:3.无重复字符的最长子串
    LeetCode:3.无重复字符的最长子串优化用kmp解题步骤用双指针维护一个滑动窗囗,用来剪切子串。不断移动右指针,遇到重复字符,就把左指针移动到重复字符的下一位。过程中,记录所有窗口的长度,并返回最大值。时间复杂度:O(n)空间复杂度:O(m),m是字符串中不重复字符的个数varlengthOfLonge......
  • 【Leetcode 热题 100】739. 每日温度
    问题背景给定一个整数数组tempera......
  • 【Leetcode 每日一题】3270. 求出数字答案
    问题背景给你三个正整数num1num_1num1​,......
  • Leetcode刷题的一些记录(Java)
    Leetcode刷题一、理论:1.数组:https://programmercarl.com/数组理论基础.htmlC++中二维数组在地址空间上是连续的。像Java是没有指针的,同时也不对程序员暴露其元素的地址,寻址操作完全交给虚拟机。所以看不到每个元素的地址情况,这里我以Java为例,也做一个实验。publicstatic......
  • LeetCode:349.两个数组的交集
    集合是什么?一种无序且唯一的数据结构。ES6中有集合,名为Set。集合的常用操作:去重、判断某元素是否在集合中、求交集letarr=[1,2,2,4,5,6,7,8,9,10]letunRepeat=[...newSet(arr)]console.log(unRepeat)letset1=newSet([1,2,3])letset2=newSet([3,4,5])console.log(se......
  • LeetCode:141.环形链表
    //双指针快+1=慢trueclassListNode{constructor(val,next){this.val=(val===undefined?0:val)this.next=(next===undefined?null:next)}}varhasCycle=function(head){letfast=headletslow=headwhile(......
  • LeetCode:83.删除排序链表中的重复元素
    LeetCode:83.删除排序链表中的重复元素classListNode{constructor(val,next){this.val=(val===undefined?0:val)this.next=(next===undefined?null:next)}}vardeleteDuplicates=function(head){letp=head//head......
  • 二叉树层序遍历 Leetcode102.二叉树的层序遍历
    二叉树的层序遍历相当于图论的广度优先搜索,用队列来实现(二叉树的递归遍历相当于图论的深度优先搜索)102.二叉树的层序遍历给你二叉树的根节点 root ,返回其节点值的 层序遍历 。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[......
  • LeetCode:206.反转链表
    flowchartTDA[开始]-->B{p1是否为空}B-->|No|C[保存p1.next到temp]C-->D[将p1.next指向p2]D-->E[更新p2为p1]E-->F[更新p1为temp]F-->BB-->|Yes|G[返回p2]LeetCode:206.反转链表/***Definitionforsingly-linkedlist.*functionLi......
  • LeetCode算法题:删除排序链表中的重复元素
    题目描述下面是给定的一段代码 /***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode(intval,ListNodenext){this.val......