【LeetCode刷题笔记(8-1)】【Python】【接雨水】【动态规划】【困难】
文章目录
- 引言
- 接雨水
- 题目描述
- 提示
- 解决方案1:【动态规划】
- 结束语
接雨水
引言
编写通过所有测试案例的代码并不简单,通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例,但如果不了解代码背后的思考过程,那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷,是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正,因为我知道我的观点可能并不完全正确,您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示,我也会感到非常荣幸。同时,我也希望我的分享能够激发您的灵感和思考,让我们一起在编程的道路上不断前行~
接雨水
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

图片来源
提示
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
解决方案1:【动态规划】

通过观察图像,我们可以发现红色方框部分与木桶的形态颇为相似。让我们富有想象力地将最左侧高度为2的柱子视作木桶的左侧板,而将最右侧高度为3的柱子视作木桶的右侧板。基于深入人心的【木桶原理】,一个木桶的装水量总是受限于其最短的那块木板。这就意味着,木桶内的水柱高度+柱子高度与左侧板的高度相等时,即达到装水的极限。
更为精妙的是,对于图中的每个位置i,我们都可以将其左侧最高的柱子想象为木桶的左侧板,而将右侧最高的柱子视为木桶的右侧板。这样一来,每个位置的水柱高度+柱子高度height[i]之和,便取决于左侧板和右侧板中较低的那个,恰如木桶原理中所蕴含的深邃智慧。
问题1:对于每个位置i,如何获取其左侧最高柱子的高度left_max[i]和右侧最高柱子的高度right_max[i]呢?
可以通过两次遍历数组height进行获取,代码如下:
# 木桶理论
# 对于位置i,left_max[i]记录的是其左侧最高柱子的高度
left_max = [0] # 对于第0根柱子,其左侧没有柱子,默认其左侧最高柱子的高度为0
# 对于位置n-1-i,right_max[i]记录的是其右侧最高柱子的高度
right_max = [0] # 对于最后一根柱子,其右侧没有柱子,默认其右侧最高柱子的高度为0n = len(height)
# 顺序遍历
for i in range(1, n):# 对于位置i,left_max[-1]记录的是位置i-1其左侧最高柱子的高度---> 只需要和位置i-1的高度height[i-1]进行比较并取最大值即可得到位置i其左侧最高柱子的高度left_max.append(max(left_max[-1], height[i-1]))
# 逆序遍历
for i in range(n-2, -1, -1):# 对于位置i,right_max[-1]记录的是位置i+1其右侧最高柱子的高度---> 只需要和位置i+1的高度height[i+1]进行比较并取最大值即可得到位置i其右侧最高柱子的高度right_max.append(max(right_max[-1], height[i+1]))
# 因为是逆序遍历,需要将结果反转 ---> 反转后, right_max[i]记录的是位置i其右侧最高柱子的高度
right_max = right_max[::-1]# 验证结果
for i in range(n):print("对于第{}根柱子,其高度为{}, 其左侧最高的柱子高度是{},其右侧最高的柱子高度是{}".format(i, height[i], left_max[i], right_max[i]))
运行结果:

观察上图的输入height以及标准输出,可以发现算法成功获取到每个位置i的左侧最高柱子的高度left_max[i]和右侧最高柱子的高度right_max[i],有了这些已知条件后,对于每个位置i,我们可以通过min(left_max[i], right_max[i]) - height[i]得到位置i的水柱高度。
完整代码如下:
class Solution:def trap(self, height: List[int]) -> int:if not height:return 0# 木桶理论# 对于位置i,left_max[i]记录的是其左侧最高柱子的高度left_max = [0] # 对于第0根柱子,其左侧没有柱子,默认其左侧最高柱子的高度为0# 对于位置n-1-i,right_max[i]记录的是其右侧最高柱子的高度right_max = [0] # 对于最后一根柱子,其右侧没有柱子,默认其右侧最高柱子的高度为0n = len(height)# 顺序遍历for i in range(1, n):# 对于位置i,left_max[-1]记录的是位置i-1其左侧最高柱子的高度---> 只需要和位置i-1的高度height[i-1]进行比较并取最大值即可得到位置i其左侧最高柱子的高度left_max.append(max(left_max[-1], height[i-1]))# 逆序遍历for i in range(n-2, -1, -1):# 对于位置i,right_max[-1]记录的是位置i+1其右侧最高柱子的高度---> 只需要和位置i+1的高度height[i+1]进行比较并取最大值即可得到位置i其右侧最高柱子的高度right_max.append(max(right_max[-1], height[i+1]))# 因为是逆序遍历,需要将结果反转 ---> 反转后, right_max[i]记录的是位置i其右侧最高柱子的高度right_max = right_max[::-1]# 获取每个位置i的水柱高度total_rain = 0for i in range(n):water_height = min(left_max[i], right_max[i]) - height[i] # 水柱高度计算公式(根据木桶原理)if water_height > 0: # 水柱高度大于0才有意义total_rain += water_heightreturn total_rain
运行结果:

复杂度分析
- 时间复杂度:O(N),其中 N 是数组
height元素的数量。 - 空间复杂度:O(N)
- 需要存放每个位置左/右侧最高柱子的高度 ===> O(N)
结束语
- 亲爱的读者,感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见,因此在这里鼓励您对我们的博客进行评论。
- 您的建议和看法对我们来说非常重要,这有助于我们更好地了解您的需求,并提供更高质量的内容和服务。
- 无论您是喜欢我们的博客还是对其有任何疑问或建议,我们都非常期待您的留言。让我们一起互动,共同进步!谢谢您的支持和参与!
- 我会坚持不懈地创作,并持续优化博文质量,为您提供更好的阅读体验。
- 谢谢您的阅读!
相关文章:
【LeetCode刷题笔记(8-1)】【Python】【接雨水】【动态规划】【困难】
文章目录 引言接雨水题目描述提示 解决方案1:【动态规划】结束语 接雨水 引言 编写通过所有测试案例的代码并不简单,通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例,但如果不了解代码背后的思考过程,那么这些代…...
pycharm通过ssh连接远程服务器的docker容器进行运行和调试代码
pycharm连接远程服务器的docker容器通常有两种方法: 第一种:pycharm通过ssh连接已在运行中的docker容器 第二种:pycharm连接docker镜像,pycharm运行代码再自动创建容器 第一种方法比较通用简单,作者比较推崇。 条件…...
Chrome2023新版收藏栏UI改回旧版
版本 120.0.6099.109(正式版本)Chrome浏览器菜单新版、旧版的差异 想要将书签、功能内容改回旧版的朋友可以网址栏输入:「chrome://flags」,接着搜寻「Chrome Refresh 2023」。 最后将 Chrome Refresh 2023、Chrome Refresh 2023…...
WebSocket与JavaScript:实现实时获取位置
一、WebSocket介绍 WebSocket是一种在单个TCP连接上进行全双工通信的协议。与传统的HTTP请求相比,WebSocket能够在服务器和客户端之间建立持久连接,实现实时数据传输。WebSocket提供了较低的延迟和高效的数据传输。在实时舆情监测中,它能够实…...
一种解决Qt5发布release文件引发的无法定位程序输入点错误的方法
目录 本地环境问题描述分析解决方案 本地环境 本文将不会解释如何利用Qt5编译生成release类型的可执行文件以及如何利用windeployqt生成可执行的依赖库,请自行百度。 环境值操作系统Windows 10 专业版(22H2)Qt版本Qt 5.15.2Qt Creator版本5.0…...
UE4/UE5 日志插件(基于spdlog)
1 解决问题 对于高频日志序列化到本地的需求,spdlog肯定完美满足。 源码地址:https://github.com/gabime/spdlog 博主下载的版本为 spdlog-1.12.0,各位大佬可以根绝自己爱好选择。 2 过程介绍 大概目录: SpdlogLibC目录下是对…...
微信小程序ios中非cover组件点击重复触发地图tap事件
现象: map中使用view组件的click事件会重复触发地图的tap组件,只在ios上出现 <map id"maps" style"width: 100vw;height: 100vh;" :latitude"latitude" :longitude"longitude":markers"markers"…...
7.26 SpringBoot项目实战【还书】
文章目录 前言一、编写控制器二、编写服务层三、Git提交前言 本文是项目实战 业务接口 的最后一篇,上文 曾说过【还书】的 入口是【我的借阅记录】,因为【还书】是基于一次借阅记录而言,另外在4.2 数据库设计 曾分析过【还书】的业务场景,需要执行两步操作: 更新【借阅记…...
Golang中使用errors返回调用堆栈信息
Golang的errors包返回堆栈信息 标准库errors提供了处理错误的方法。比如常用的 func New(text string) error 用该方法处理错误信息,就只会输出自定义的 text 到控制台或者日志文件,没有其它辅助排查的信息输出,所以常规我们就只能根据 te…...
Web前端-HTML(常用标签)
文章目录 1. HTML常用标签1.1 排版标签1)标题标签h (熟记)2)段落标签p ( 熟记)3)水平线标签hr(认识)4)换行标签br (熟记)5)div 和 span标签(重点)6)排版标签总结 1.2 标签属性1.3 图像标签img (重点)1.4 链…...
一 OpenCV中的数据类型
1. cv::Mat 2. cv::Point 主要用来表示二维点,也有表示三维点的模板类型; cv::Point p(int, int) 最常用 ① cv::Point_<T> ② cv::Point2i cv::Point_<int> ③ cv::Point2f cv::Point_<float> ④ cv::Point2d …...
59. 螺旋矩阵 II(java实现,史上最详细教程,想学会的进!!!)
今天来分享一下螺旋矩阵的解题思路及代码的实现。 题目描述如下: 首先拿到这道题,首先不要慌张,我们来仔细分析一下会发现并没有那么难。 首先看下边界的元素是1、2、3递增的,那么我们也许可以根据这一点先把边界的元素一个一个给…...
vue 将后端返回的二进制流进行处理并实现下载
什么是二进制流文件? 二进制文件是一种计算机文件格式,它的数据以二进制形式存储,与文本文件不同。二进制文件可以包含任意类型的数据,例如图像、音频、视频、可执行文件、压缩文件等,而文本文件则仅仅包含 ASCII 码或…...
PyCharm连接远程服务器
要求:PyCharm专业版才支持远程服务 一、创建远程连接 先建立本地与远程服务器之间的SSH连接 1、配置连接 2、建立SSH连接,选择文件传输协议 SFTP 3、设置服务器名(可以随意命名) 4、配置 SSH连接 点击 172.18.1.202 配置…...
使用Qt制作网易云播放器的歌曲排行界面
!!!直接上图!!! !!!直接上图!!! !!!直接上图!!! 网易云排行榜…...
【.NET Core】特性(Attribute)详解
【.NET Core】特性(Attribute)详解 文章目录 【.NET Core】特性(Attribute)详解一、概述二、编写自定义属性2.1 自定义特性的主要步骤2.2 应用AttributeUsageAttributeAttributeTargets 成员Inherited属性AllowMultiple属性 三、声…...
【C++】POCO学习总结(十九):哈希、URL、UUID、配置文件、日志配置、动态库加载
【C】郭老二博文之:C目录 1、哈希 1.1 说明 std::map和std::set 的性能是:O(log n) POCO哈希的性能比STL容器更好,大约快两; POCO中对应std::map的是:Poco::HashMap; POCO中对应std::set的是 Poco::Hash…...
1846_安全SPI
Grey 全部学习内容汇总:GitHub - GreyZhang/g_embedded: some embedded basic knowledge. 1846_安全SPI SPI是一种常见的通信方式,在汽车电子中比较常用。但是如果涉及到安全相关的设计,可能得考虑更多。而SPI协议本身没有很好的标准化&am…...
SQL Server ,使用递归查询具有层级关系的数据。
假设我们有一个表格 Employees,其中包含员工的层级关系信息,每一行包括员工的ID、姓名以及上级员工的ID。 下面是一个示例表格及其数据: Employees ---------------------- EmployeeID | Name | ManagerID ---------------------- 1 …...
【参数汇总】mysql服务端/客户端常见优化参数
mysql服务端参数 1、innodb_buffer_pool_size (innodb索引buffer pool缓冲区大小) 默认大小为128M, 官方推荐其配置为系统内存的 50% 到 75% 。 一般innodb_buffer_pool_size要结合以下两个参数来设置: innodb_buffer_pool_ch…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
大数据治理的常见方式
大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法,以下是几种常见的治理方式: 1. 数据质量管理 核心方法: 数据校验:建立数据校验规则(格式、范围、一致性等)数据清洗&…...
