面试经典算法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项目模板…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
