当前位置: 首页 > news >正文

接雨水问题

接雨水问题

问题背景

LeetCode 42. 接雨水
接雨水问题是一个经典的计算雨水滞留量的问题,通常使用柱状图来表示不同高度的柱子。在下雨的情况下,柱子之间的凹陷部分能够存储雨水,问题的目标是计算这些柱子所能接收的雨水总量。

相关知识

在解决接雨水问题之前,需要了解以下几个关键概念:

  • 柱状图:表示不同高度的柱子,通常由一个整数数组表示,每个元素代表柱子的高度。
  • 雨水滞留:在柱状图中,两根柱子之间的凹陷部分可以存储雨水,我们需要计算这些凹陷部分的总容量。

问题介绍

给定一个由非负整数表示的柱状图,每个柱子的宽度为 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

解题思路

接雨水问题的解决思路通常使用双指针法。具体步骤如下:

  1. 初始化左指针 left 和右指针 right,并初始化左侧最大高度 leftMax 和右侧最大高度 rightMax 为 0。
  2. 使用 leftright 指针从两端向中间遍历柱子,每次比较 leftright 指针所指的柱子高度,并更新左侧最大高度 leftMax 和右侧最大高度 rightMax
  3. 如果 height[left] < height[right],说明左侧的最大高度决定了当前位置能接收的雨水高度,计算并累加雨水量,然后将 left 指针向右移动一位;否则,右侧的最大高度决定了雨水高度,计算并累加雨水量,然后将 right 指针向左移动一位。
  4. 重复步骤 2 和步骤 3,直到 leftright 指针相遇。

最终,累加的雨水量即为所求的雨水滞留量。

代码实现

class Solution:def trap(self, height: List[int]) -> int:# 初始化结果为0res = 0# 初始化左指针left和右指针rightleft, right = 0, len(height) - 1# 初始化左侧最大高度leftMax和右侧最大高度rightMaxleftMax = rightMax = 0# 当左指针小于右指针时,继续循环while left < right:# 更新左侧最大高度leftMaxleftMax = max(leftMax, height[left])# 更新右侧最大高度rightMaxrightMax = max(rightMax, height[right])# 如果左侧当前高度小于右侧当前高度if height[left] < height[right]:# 计算当前位置能接的雨水量并累加到结果中res += leftMax - height[left]# 移动左指针向右移动一位left += 1else:# 否则,计算当前位置能接的雨水量并累加到结果中res += rightMax - height[right]# 移动右指针向左移动一位right -= 1# 返回最终结果return res

上述 Python 代码实现了双指针法的思路。首先,我们初始化左指针 left 和右指针 right,以及左侧最大高度 leftMax 和右侧最大高度 rightMax。然后,使用指针从两端向中间遍历柱子,计算并累加雨水量。最后,返回累加的雨水量作为结果。

时间和空间复杂度

  • 时间复杂度:双指针法的时间复杂度为 O(n),其中 n 是柱子的数量。
  • 空间复杂度:双指针法只需要常数级别的额外空间,空间复杂度为 O(1)。

结论

接雨水问题是一个经典的算法问题,通过双指针法,我们可以高效地计算雨水滞留量。

相关文章:

接雨水问题

接雨水问题 问题背景 LeetCode 42. 接雨水 接雨水问题是一个经典的计算雨水滞留量的问题&#xff0c;通常使用柱状图来表示不同高度的柱子。在下雨的情况下&#xff0c;柱子之间的凹陷部分能够存储雨水&#xff0c;问题的目标是计算这些柱子所能接收的雨水总量。 相关知识 …...

小谈设计模式(9)—工厂方法模式

小谈设计模式&#xff08;9&#xff09;—工厂方法模式 专栏介绍专栏地址专栏介绍 工厂方法模式角色分类抽象产品&#xff08;Abstract Product&#xff09;具体产品&#xff08;Concrete Product&#xff09;抽象工厂&#xff08;Abstract Factory&#xff09;具体工厂&#x…...

Android etc1tool之png图片转换pkm 和 zipalign简介

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、etc1tool2.1、用法 三、zipalign3.1 使用 四…...

Spring Boot快速入门:构建简单的Web应用

SpringBoot Spring Boot是一个用于简化Spring应用程序开发的框架&#xff0c;它通过提供开箱即用的配置和一组常用的功能&#xff0c;使得构建高效、可维护的应用变得非常容易。在本篇博客中&#xff0c;我们将一步步地介绍如何快速入门Spring Boot&#xff0c;并构建一个简单的…...

JAVA 泛型、序列化和复制

泛型提供了编译时类型安全检测机制&#xff0c;该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型&#xff0c;也就是说所操作的数据类型被指定为一个参数。比如我们要写一个排序方法&#xff0c;能够对整型数组、字符串数组甚至其他任何类型的数组进行排序&a…...

以太网基础学习(二)——ARP协议

一、什么是MAC地址 MAC地址&#xff08;英语&#xff1a;Media Access Control Address&#xff09;&#xff0c;直译为媒体访问控制位址&#xff0c;也称为局域网地址&#xff08;LAN Address&#xff09;&#xff0c;MAC位址&#xff0c;以太网地址&#xff08;Ethernet Addr…...

【Java-LangChain:使用 ChatGPT API 搭建系统-4】评估输入-分类

第三章&#xff0c;评估输入-分类 如果您正在构建一个允许用户输入信息的系统&#xff0c;首先要确保人们在负责任地使用系统&#xff0c;以及他们没有试图以某种方式滥用系统&#xff0c;这是非常重要的。 在本章中&#xff0c;我们将介绍几种策略来实现这一目标。 我们将学习…...

嵌入式Linux应用开发-驱动大全-第一章同步与互斥③

嵌入式Linux应用开发-驱动大全-第一章同步与互斥③ 第一章 同步与互斥③1.4 Linux锁的介绍与使用1.4.1 锁的类型1.4.1.1 自旋锁1.4.1.2 睡眠锁 1.4.2 锁的内核函数1.4.2.1 自旋锁1.4.2.2 信号量1.4.2.3 互斥量1.4.2.4 semaphore和 mutex的区别 1.4.3 何时用何种锁1.4.4 内核抢占…...

树的存储结构以及树,二叉树,森林之间的转换

目录 1.双亲表示法 2.孩子链表 3.孩子兄弟表示法 4.树与二叉树的转换 &#xff08;1&#xff09;树转换为二叉树 &#xff08;2&#xff09;二叉树转换成树 5.二叉树与森林的转化 &#xff08;1&#xff09;森林转换为二叉树 以下树为例 1.双亲表示法 双亲表示法定义了…...

【AI视野·今日NLP 自然语言处理论文速览 第四十二期】Wed, 27 Sep 2023

AI视野今日CS.NLP 自然语言处理论文速览 Wed, 27 Sep 2023 Totally 50 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Attention Satisfies: A Constraint-Satisfaction Lens on Factual Errors of Language Models Authors Mert …...

华为云云耀云服务器L实例评测|部署个人在线电子书库 calibre

华为云云耀云服务器L实例评测&#xff5c;部署个人在线电子书库 calibre 一、云耀云服务器L实例介绍1.1 云服务器介绍1.2 应用场景1.3 支持镜像 二、云耀云服务器L实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置 三、部署 calibre3.1 calibre 介绍3.2 Docker 环境搭建3.3 c…...

代码随想录刷题 Day28

216.组合总和III 和前一个题一样&#xff0c;照着自己就能写出来&#xff0c;就多了一个判断结果是不是等于n的逻辑。有两个地方可以剪纸&#xff0c;一个是当和已经大于要找的时候直接返回&#xff0c;另一个是当剩余元素少于三个的时候直接返回&#xff08;第一层递归是少于…...

【生命周期】

生命周期 1 引出生命周期2 分析生命周期3 总结生命周期 1 引出生命周期 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta …...

【C语言 模拟实现memcpy函数、memcpy函数】

C语言程序设计笔记---027 C语言之模拟实现memcpy函数、memcpy函数1、介绍memcpy函数1.1、模拟实现memcpy函数 2、介绍memmove函数2.1、模拟实现memmove函数 3、结语 C语言之模拟实现memcpy函数、memcpy函数 前言&#xff1a; 通过C语言内存函数的知识&#xff0c;这篇将对memc…...

opencv视频文件的读取,处理与保存

文章目录 opencv视频文件的读取&#xff0c;处理与保存一、视频文件的读取&#xff1a;1、cv::VideoCapture是OpenCV库中用于处理视频输入的类&#xff0c;它提供了一种简单的方法来从摄像头&#xff0c;视频文件、或图像序列中读取帧&#xff1b;&#xff08;1&#xff09;打开…...

java - 七大比较排序 - 详解

前言 本篇介绍了七大比较排序&#xff0c;直接插入排序&#xff0c;希尔排序&#xff0c;冒泡排序&#xff0c;堆排序&#xff0c;选择排序&#xff0c;快速排序&#xff0c;归并排序&#xff0c;一些简单思想代码实现&#xff0c;如有错误&#xff0c;请在评论区指正&#xf…...

项目集成七牛云存储sdk

以PHP为例 第一步&#xff1a;下载sdk PHP SDK_SDK 下载_对象存储 - 七牛开发者中心 sdk下载成功之后&#xff0c;将sdk放入项目中&#xff0c;目录选择以自己项目实际情况而定。 注意&#xff1a;在examples目录中有各种上传文件的参考示例&#xff0c;这里我们主要参考的是…...

docker-compose一键启动neo4j

下载镜像 docker pull neo4j:3.5.22-community 编写配置文件 参考文档 编写docker-compose.yml文件 version: "3"services:neo4j:image: neo4j:3.5.22-communitycontainer_name: neo4j restart: alwaysports:- 7474:7474- 7687:7687environment:- NEO4J_AUTH:ne…...

深入剖析@ConfigurationProperties注解

当我们构建Spring Boot应用程序时&#xff0c;配置属性通常是不可或缺的一部分。Spring Boot提供了多种方式来管理这些属性&#xff0c;其中之一是使用ConfigurationProperties注解。这篇博客将详细解释ConfigurationProperties注解以及如何使用它来管理和映射配置属性。 什么…...

北京开发APP需要多少钱

北京开发一个移动应用&#xff08;APP&#xff09;的费用因多种因素而异&#xff0c;包括项目的规模、复杂性、所需功能、设计要求、技术选择、开发团队的经验和地理位置等。一般来说&#xff0c;北京的APP开发费用通常较高&#xff0c;因为这是中国的主要技术和创新中心之一&a…...

self-attention、transformer、bert理解

参考李宏毅老师的视频 https://www.bilibili.com/video/BV1LP411b7zS?p2&spm_id_frompageDriver&vd_sourcec67a2725ac3ca01c38eb3916d221e708 一个输入&#xff0c;一个输出&#xff0c;未考虑输入之间的关系&#xff01;&#xff01;&#xff01; self-attention…...

junit @ExcludePackages排除多个包

在JUnit中&#xff0c;可以使用ExcludePackages注解来排除多个包。该注解可以用在测试类或测试方法上。 如果要排除多个包&#xff0c;可以在ExcludePackages注解的value属性中使用数组来指定要排除的包名。例如&#xff0c;要排除包com.example.package1和com.example.packag…...

Explain执行计划字段解释说明---select_type、table、patitions字段说明

1、select_type的类型有哪些 2、select_type的查询类型说明 1、SIMPLE 简单的 select 查询,查询中不包含子查询或者UNION 2、PRIMARY 查询中若包含任何复杂的子部分&#xff0c;最外层查询则被标记为Primary 3、DERIVED 在FROM列表中包含的子查询被标记为DERIVED(衍生)&…...

云原生微服务 第六章 Spring Cloud Netflix Eureka集成远程调用、负载均衡组件OpenFeign

系列文章目录 第一章 Java线程池技术应用 第二章 CountDownLatch和Semaphone的应用 第三章 Spring Cloud 简介 第四章 Spring Cloud Netflix 之 Eureka 第五章 Spring Cloud Netflix 之 Ribbon 第六章 Spring Cloud 之 OpenFeign 文章目录 系列文章目录前言1、OpenFeign的实现…...

四、2023.9.30.C++面向对象end.4

文章目录 49、 简述一下什么是常函数&#xff0c;有什么作用&#xff1f;50、 说说什么是虚继承&#xff0c;解决什么问题&#xff0c;如何实现&#xff1f;51、简述一下虚函数和纯虚函数&#xff0c;以及实现原理&#xff1f;52、说说纯虚函数能实例化吗&#xff0c;为什么&am…...

【Java】包

package 包&#xff08;package&#xff09;:其实就是文件夹。 作用&#xff1a;对类进行分类管理。 包的定义格式 格式&#xff1a;package 包名&#xff08;多级包用 . 分开&#xff09; 范例&#xff1a;package com.mayikt.demo01 带包的Java类编译和执行 1. 手动建包 安装…...

Hive【Hive(二)DML】

启动 hive 命令行&#xff1a; hive DML 数据操作 1、数据导入 1.1、向表中装载数据&#xff08;load&#xff09; 语法&#xff1a; hive> load data [local] inpath 数据的path [overwrite] into table student [partition (partcol1val1,…)];&#xff08;1&#x…...

HTTP的请求方法,空行,body,介绍请求报头的内部以及粘包问题

目录 一、GET与POST简介 二、空行和body 三、初识请求报头以及粘包问题 四、认识请求报头剩余部分 一、GET与POST简介 GET https://www.sogou.com/HTTP/1.1 请求报文中的方法&#xff0c;是最常规的方法&#xff08;获取资源&#xff09; POST&#xff1a;传输实体主体的方法…...

win10 ip设置

百度安全验证...

alibaba dragonwell jdk

阿里巴巴Dragonwell8快速指南 dragonwell-project/dragonwell8 Wiki GitHub 阿里巴巴Dragonwell8用户指南 dragonwell-project/dragonwell8 Wiki GitHub 阿里巴巴Dragonwell8常见问题 dragonwell-project/dragonwell8 Wiki GitHub...