首页 > 其他分享 >每日leetcode--接雨水

每日leetcode--接雨水

时间:2024-03-13 20:32:28浏览次数:34  
标签:right 计算 -- 雨水 height 数组 leetcode left

引言

接雨水问题是一个经典的算法问题,它要求我们计算给定一组不同高度的墙壁时,这些墙壁之间能够蓄积多少雨水。解决这个问题的方法有很多,其中一种常见的解法是通过辅助数组来记录每个位置的左右最大高度,并计算每个位置上方能够蓄积的雨水量。

问题描述

假设我们有一个非负整数数组height,其中每个元素表示墙壁的高度。我们需要计算这些墙壁之间能够蓄积多少雨水。

题目链接:. - 力扣(LeetCode)

思路:辅助数组法

接下来,我们将介绍一种解决接雨水问题的常见方法,即通过辅助数组来记录每个位置的左右最大高度,并计算每个位置上方能够蓄积的雨水量。

python代码

class Solution:
    def trap(self, height: List[int]) -> int:
        # left, right 分别存储一点左,右边最高墙壁
        left=[]
        right=[]
        #ans为返回值
        ans=0
        lmax, rmax=0,0
        left.append(0)
        for i in range(1,len(height)):
            lmax=max(lmax, height[i-1])
            left.append(lmax)
        right.append(0)
        for i in range(len(height)-2, -1, -1):
            rmax=max(rmax, height[i+1])
            right.append(rmax)
        right=right[::-1]
        print(f"left={left}")
        print(f"righ={right}")

        for i in range(len(height)):
            ans+=max(0, min(left[i], right[i])-height[i])


        return ans

详细步骤解释:

  1. 我们首先创建了两个辅助数组leftright,用于分别存储每个位置的左侧和右侧最大高度。
  2. 然后我们通过遍历数组,计算每个位置的左侧最大高度,并将结果存入left数组中。
  3. 接着,我们通过逆序遍历数组,计算每个位置的右侧最大高度,并将结果存入right数组中。
  4. right数组进行反转,以便与left数组对应位置进行比较。
  5. 最后,我们再次遍历数组,计算每个位置上方能够蓄积的雨水量,并累加到变量ans中。
  6. 最终,我们返回计算得到的雨水总量ans作为结果。

示例与分析: 假设我们有一个高度数组[0,1,0,2,1,0,1,3,2,1,2,1],使用上述算法进行计算可以得到结果为6。具体的计算过程如下:

height=[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
left = [0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 
right = [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0] 
#计算每个位置上方能够蓄积的雨水量: 
[0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 0, 0]

从示例中可以看出,计算得到的雨水总量为6,即该数组表示的墙壁之间能够蓄积的雨水量。

复杂度分析:

  • 时间复杂度:该算法需要遍历两次输入数组,分别计算左右最大高度,以及遍历一次数组计算每个位置上方的雨水量。因此,时间复杂度为O(n),其中n是输入数组的长度。
  • 空间复杂度:该算法使用了两个额外的辅助数组leftright,它们的长度与输入数组相同。因此,空间复杂度为O(n)。

结论: 通过辅助数组法,我们可以有效地解决接雨水问题。该方法利用了辅助数组存储每个位置的左右最大高度,并通过遍历数组计算每个位置上方能够蓄积的雨水量。这种方法简单、直观,并且具有较好的时间复杂度和空间复杂度。

展望: 除了辅助数组法之外,还有其他解决接雨水问题的方法。例如,可以使用双指针法、栈等数据结构来解决该问题。在未来的研究和实践中,我们可以进一步探究这些方法,并比较它们的优缺点,以寻找更加高效的解决方案。

详细题解:. - 力扣(LeetCode)


标签:right,计算,--,雨水,height,数组,leetcode,left
From: https://blog.csdn.net/li_peixiansang/article/details/136661672

相关文章

  • 使用Julia语言展示几何平均值与算数平均值在实际应用中的差别(采用注册计量师考试试题
    理论部分在注册计量师考试中有一道试题,大体内容为:现在有一块砝码在等臂天平上进行测量,第一次测得值是19.6g,调换两边位置后的测得值是19.7g,天平最终测得检测样品的重量为多少? 个别同事可能会将算数平均值作为这个砝码的最终测量值,但实际应当使用几何平均值的方式计算,算数......
  • Java基础笔记
    jdk、jre、jvm三者之间的关系Java语言开发程序能够做到一次编写处处运行(能够跨平台运行)java中的注释  Java中的关键字和保留字  ......
  • 浅谈HTTP 和 HTTPS (中间人问题)
    前言由于之前的文章已经介绍过了HTTP,这篇文章介绍HTTPS相对于HTTP做出的改进开门见山:HTTPS是对HTTP的加强版主要是对一些关键信息进行了加密一.两种加密方式1.对称加密公钥+明文=密文密文+公钥=明文2.非对称加密举个例子就好比小区邮箱提供......
  • 3.2 Beautiful Soup 的使用
    目录一、BeautifulSoup的简介二、解析器三、基本使用四、节点选择器1 选择元素2获取名称、属性、文本内容五、方法选择器1 find_all传入name 节点名传入attrs 属性传入text 2find六、CSS选择器1实例2获取属性3获取文本七、结语一、Beautif......
  • Java 引用变量的比较
    在Java中,当你使用双引号直接创建字符串时,如:Strings=“LXHYouth”;Strings2=“LXHYouth”;使用==运算符比较这两个引用时,结果为true然而,当你使用new关键字创建字符串对象时,情况就有所不同了:Strings3=newString(“LXHYouth”);//使用new关键字,s3指向堆中的一......
  • linux:services服务器配置
    1.环境准备。配置selinux和防火墙vim/etc/selinux/configSELINUX=permissiveyum-yremovefirewalldip地址基础[root@server~]#ipaddressshow[root@server~]#ipas临时添加IP地址[root@server~]#ipaddressadd192.168.10.1/24deveth......
  • 综合:配置高可用、负载均衡
    环境说明:LVS-DR模式client1:eth0->192.168.88.10lvs1:eth0->192.168.88.5lvs2:eth0->192.168.88.6web1:eth0->192.168.88.100web2:eth0->192.168.88.200环境准备#关闭2台web服务器上的keepalived,并卸载[root@pubservercluster]#vim08-rm-keepalived.yml---......
  • IIC SPI UART RS232 RS485的差异简介
    UART串口通信:异步通信,两根线(RXDTXD)交叉连接进行点对点的通信,通信双方要设置好相同的波特率(其实不用完全一样也可以只要相差不大,毕竟是通信双方不是同一时钟),发送数据一般是发送8位,有起始位、数据、检验、停止位。串口通信的抗干扰能力差,通信距离短。RS232协议:编程还是按串......
  • 操作符进阶
    补充操作符:1.加减乘除后赋值:+=,-=,=,/=直接上强度,四个操作符一起讲。#include<stdio.h>intmain(){ inta=10; a+=10;//和a=a+10一样 a-=5;//和a=a-10一样 a*=3;//和a=a*10一样 a/=5;//和a=a/10一样 printf("%d",a);}为了分析代码方便直接上注释了分析代码:a=10,操作......
  • 与LDO背道而驰的DCDC
    LDO:低压差线性稳压器,比较常见的芯片为117,LDO的特性就如他的中文名一样,因为他的原理其实就是类似通过控制一个可变电阻来控制电压,从而达到稳压的效果,因此稳定的电压差不能太大否则电流就会过大,所以LDO的稳压器一般发热比较严重,损耗比较高,DCDC:开关稳压器,比较常见的芯片是2596,D......