面试经典算法150题系列-接雨水
接雨水
给定 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

实现思路:
接雨水问题的实现思路主要基于以下观察:
-
局部最大值:一个柱子能接雨水的量取决于它左右两边最高的柱子高度中的较小值(因为雨水只能在两者较低的一侧积累)。
-
双指针:使用两个指针
left和right分别从数组的两端向中间遍历。这样可以同时考虑左右两边的柱子高度。 -
维护最大高度:在遍历过程中,维护两个变量
leftMax和rightMax来记录从左边和右边开始遍历到目前为止遇到的最高的柱子高度。 -
计算雨水量:当遍历到的柱子高度小于
leftMax或rightMax时,可以计算出当前柱子能接的雨水量,即min(leftMax, rightMax) - height[i]。如果柱子高度大于等于记录的最大高度,则更新leftMax或rightMax。 -
累加雨水量:将每次计算出的雨水量累加到总雨水量
ans中。 -
边界条件:如果输入数组为空或长度为0,则直接返回0,因为没有柱子可以接雨水。
具体步骤如下:
-
初始化两个指针
left和right分别指向数组的开始和结束位置,以及两个变量leftMax和rightMax为0。 -
使用一个循环,当
left小于right时继续执行:- 如果
height[left] < height[right],则移动left指针,并更新leftMax:- 如果当前柱子高度大于等于
leftMax,则更新leftMax。 - 否则,计算当前柱子能接的雨水量,并累加到
ans。
- 如果当前柱子高度大于等于
- 否则,移动
right指针,并更新rightMax:类似地更新rightMax和累加雨水量。
- 如果
-
当
left和right相遇时,遍历结束,返回计算出的总雨水量ans。
这种双指针的方法时间复杂度为 O(n),其中 n 是数组 height 的长度,因为每个元素只被遍历一次。空间复杂度为 O(1),因为只需要常数级别的额外空间。
思路模拟:
让我们通过一个模拟来更深入地理解接雨水问题的解决思路。假设我们有以下高度数组:
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
我们的目标是找到这些柱子之间可以接多少雨水。下面是一步步的模拟过程:
-
初始化两个指针
left和right分别指向数组的两端,即left = 0和right = length - 1。同时,初始化两个变量leftMax和rightMax来记录左右两边遍历过程中的最大高度,初始值设为0。 -
遍历开始:
- 当
left < right时,执行循环。 - 比较
height[left]和height[right]:- 如果
height[left] < height[right],说明我们处于左侧的较低部分,我们需要更新leftMax并可能计算左侧的雨水量。 - 如果
height[left] >= height[right],我们处于右侧的较低部分或两边高度相同,更新rightMax并可能计算右侧的雨水量。
- 如果
- 当
-
在每一步中,我们执行以下操作:
- 如果当前柱子的高度小于
leftMax,则当前柱子可以接到雨水,雨水量为leftMax - height[left]。 - 如果当前柱子的高度大于或等于
leftMax,则更新leftMax为当前柱子的高度。
- 如果当前柱子的高度小于
-
同理,对于右侧:
- 如果
height[right] < height[left],则rightMax可能更新,并且可能计算右侧的雨水量。 - 如果
height[right]更新了rightMax,则不会立即计算雨水,因为只有在移动到更矮的柱子时才会计算。
- 如果
-
重复步骤3和4,直到
left和right相遇。 -
累加每一步计算的雨水量,得到最终结果。
让我们模拟这个过程:
- 初始状态:
left = 0,right = 12,leftMax = 0,rightMax = 0,ans = 0 - 移动
left到下一个元素,leftMax更新为1(height[1])。 - 移动
right到前一个元素,rightMax更新为1(height[12])。 - 继续移动
left和right,更新leftMax和rightMax,直到它们指向相邻的元素。
下面是模拟的详细步骤:
left: 0 1 2 3 4 5 6 7 8 9 10 11 12 (right)
height: 0 1 0 2 1 0 1 3 2 1 2 1 0
leftMax: 0 1 1 2 2 2 3 3 3 2 2 1 1
rightMax: 0 0 0 0 1 1 1 2 3 3 2 1 1
ans: 0 0 0 2 3 4 4 5 6 6 5 4 3
在每一步,我们可以看到 leftMax 和 rightMax 的更新,以及计算的雨水量累加到 ans 中。最终,ans 的值是6,这就是我们可以接到的雨水总量。
请注意,这个模拟是为了演示算法的逻辑流程,实际的代码实现会使用条件语句来确定何时更新 leftMax、rightMax 以及何时计算雨水量。
实现代码:
public int trap(int[] height) {if (height == null || height.length == 0) {return 0;}int n = height.length;int left = 0, right = n - 1;int leftMax = 0, rightMax = 0;int ans = 0;while (left < right) {if (height[left] < height[right]) {// 当左边的柱子高度小于右边的柱子高度if (height[left] >= leftMax) {// 更新左边的柱子能接的雨水量leftMax = height[left];} else {// 计算当前柱子能接的雨水量,并累加到总雨水量中ans += leftMax - height[left];}left++;} else {// 右边的柱子高度不小于左边的柱子高度if (height[right] >= rightMax) {// 更新右边的柱子能接的雨水量rightMax = height[right];} else {// 计算当前柱子能接的雨水量,并累加到总雨水量中ans += rightMax - height[right];}right--;}}return ans;}
相关文章:
面试经典算法150题系列-接雨水
接雨水 给定 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,…...
【C++】 类型转换深度探索:揭开类型转换的奥秘
🌈 个人主页:Zfox_ 🔥 系列专栏:C从入门到精通 目录 一: 🚀 C语言中的类型转换 二: 🔥 为什么C需要四种类型转换 三: 🔥 C强制类型转换 🥝 3.1 st…...
深入探索Webkit的Web Authentication API:安全与便捷的融合
Web Authentication API,通常被称为WebAuthn,是一个新兴的Web标准,旨在通过提供更安全、更便捷的认证方式来改善用户的在线体验。随着Webkit对WebAuthn的支持日益增强,本文将深入探讨这一API的功能、实现方式以及如何在Webkit浏览…...
Vue - 关于v-wave 波浪动画组件
Vue - 关于v-wave 波浪动画组件 这个动画库可以在标签中添加新的v-wave属性,来让点击标签元素后添加漂亮的波纹效果,并且可以根据父元素自动形成波纹的颜色,也可以自定义波纹颜色,持续时间,透明度,触发的对…...
计算机网络408考研 2019
计算机网络408考研2019年真题解析_哔哩哔哩_bilibili 2019 1 1 1 1...
实时捕捉与追溯:得物基于 eBPF 打造云上网络连接异常摄像头
近期我们容器 SRE 团队基于 eBPF 技术建设网络连接异常感知能力,灰度上线过程中发现了生产环境 10 以上的应用配置错误、程序 Bug 等问题。在和应用负责同学同步风险过程中,大家都挺好奇我们如何实现在对应用无侵入的情况下发现服务连接异常的。本篇文档…...
ubuntu14.04图形界面配置
Ubuntu系统启动,输入用户密码后,屏幕显示彩色背景,但是始终不能进入图形界面。 如果你也遇到过这种情况,可以参照以下方法解决(在 ubuntu14.04 验证)。 同时按下 alt ctrl F1,屏幕出现 tty1&a…...
51单片机-第八节-蜂鸣器
一、什么是蜂鸣器? 蜂鸣器是一种将电信号转换为声音信号的器件,常用来产生设备的按键音、报警音等提示信号。 蜂鸣器按驱动方式可分为有源蜂鸣器和无源蜂鸣器: 有源蜂鸣器:内部自带振荡源,将正负极接上直流电压即可…...
Windows命令查看WiFi密码
查看所有已保存的WiFi网络 (以管理员身份)输入以下命令 netsh wlan show profiles查看某个WiFi网络的密码 netsh wlan show profile name"你的网络名" keyclear在输出中,在关键内容(Key Content)字段下找…...
不同环境下RabbitMQ的安装-2 ARM架构、X86架构、Window系统环境下安装RabbitMQ
ARM架构、X86架构、Window系统环境下RabbitMQ的安装 RabbitMQ安装1 Erlang语言介绍2 安装Erlang2.1 ARM架构的CentOS虚拟机中安装Erlang2.2 X86架构的CentOS虚拟机中安装Erlang2.3 Windows系统安装Erlang2.3.1 下载Erlang2.3.2 安装Erlang2.3.3 配置Erlang2.3.4 检测Erlang 3.安…...
C++(week16): C++提高:(六) Qt提高
文章目录 四、Qt的元对象系统1.元对象和MOC(1)自省 和 反射(2)Qt是怎样支持元对象系统的?(3)支持元对象系统的三个要求(4)元对象系统的功能(5)动态属性 2.信号和槽机制(1)信号与槽机制的基本原理(2)自定义信号、自定义槽函数①自定义信号②自定义槽③关联 connect (…...
go 时间转时间戳的时区设置问题
昨天遇到一个问题,在完成时间转换时间戳,在后续测试中发现转换后的时间戳转成时间后,时间发生错误,时间和转换时间不一致问题 如下: package mainimport ("fmt""time" )func main() {Start : &q…...
MySQL 常见日志清理策略
前言: MySQL 数据库服务器使用多种类型的日志来记录操作和事件,这对于故障诊断、审计和性能分析非常重要。然而,这些日志文件会随着时间的推移而不断增长,可能会占用大量的磁盘空间。因此,定期清理这些日志是必要的&a…...
3大管人绝招让你的手下心服口服
3大管人绝招让你的手下心服口服 一:差异化管理,玩弄人性 谁赞成,谁反对,看清楚谁顺从自己,谁反对自己之后,接下来要做的便是区别对待。 给听话的下属最好的资源、最轻松简单的工作、最高的待遇…...
useImperativeHandle 是什么?你可以理解为 vue3 的 expose
useImperativeHandle 确实类似于 Vue 3 的 expose,两者都用于控制子组件向父组件暴露的接口。 在 React 中,useImperativeHandle 需要与 forwardRef 一起使用,原因如下: 转发引用:forwardRef 允许父组件将 ref 传递给…...
《Techporters架构搭建》-Day05 属性校验
属性校验 前言Validated基础用法集合校验分组校验嵌套校验自定义校验器 源码地址 前言 在项目开发过程中,经常遇到需要对传递的参数进行校验,比如某个参数字段是否为空、值的取值是否在约定范围、格式是否合法等等,最原始的写法,…...
HTTP的场景实践
HTTP的场景实践:任选一个浏览器,对于其涉及的请求中的缓存策略展开具体分析 1. 强缓存: Cache-Control用于指定缓存的最长有效时间。 Expires用于指定资源过期的日期。 2. 协商缓存: ETag用于标识资源的唯一标识符,…...
MySQL:表的设计原则和聚合函数
所属专栏:MySQL学习 💎1. 表的设计原则 1. 从需求中找到类,类对应到数据库中的实体,实体在数据库中表现为一张一张的表,类中的属性对应着表中的字段 2. 确定类与类的对应关系 3. 使用SQL去创建具体的表 范式࿱…...
介绍springmvc-水文
Spring MVC 是一个基于 Java 的开源 Web 框架,它是 Spring Framework 的一部分。Spring MVC 提供了一个架构,用于开发灵活、可扩展的 Web 应用程序。 Spring MVC 的主要特点包括: 基于模型-视图-控制器(MVC)的架构&am…...
uni-app学习笔记
一、下载HBuilder https://www.dcloud.io/hbuilderx.html 上述网址下载对应版本,下载完成后进行解压,不需要安装,解压完成后,点击HBuilder X.exe文件进行运行程序 二、创建uni-app项目 此处我是按照文档创建的uni-ui项目模板…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...
FOPLP vs CoWoS
以下是 FOPLP(Fan-out panel-level packaging 扇出型面板级封装)与 CoWoS(Chip on Wafer on Substrate)两种先进封装技术的详细对比分析,涵盖技术原理、性能、成本、应用场景及市场趋势等维度: 一、技术原…...
