【力扣】42. 接雨水 <模拟、双指针、单调栈>
【力扣】42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
目录
- 【力扣】42. 接雨水
- 题解
- 暴力
- 双指针
- 单调栈
示例 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
提示:
n == height.length
1 <= n <= 2 * 1 0 4 10^4 104
0 <= height[i] <= 1 0 5 10^5 105
题解
暴力
按照列来计算的话,宽度一定是1,把每一列的雨水的高度求出来即可。
每一列雨水的高度,取决于该列左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。
min(左边柱子的最高高度,记录右边柱子的最高高度) - 当前柱子高度
min(lHeight, rHeight) - height
public class Solution {public int trap(int[] height) {int sumWater = 0;for (int i = 0; i < height.length; i++) {// 第一个柱子和最后一个柱子不接雨水if (i==0 || i== height.length - 1) {continue;}// 记录右边柱子的最高高度int rHeight = height[i];// 记录左边柱子的最高高度int lHeight = height[i];// 求左边最高柱子for (int l = i-1; l >= 0; l--) {if(height[l] > lHeight) {lHeight = height[l];}}// 求右边最高柱子for (int r = i+1; r < height.length; r++) {if (height[r] > rHeight) {rHeight = height[r];}}//每一列雨水的高度,取决于,该列左侧最高的柱子和右侧最高的柱子中 最矮的那个柱子的高度。int h = Math.min(lHeight, rHeight) - height[i];if (h > 0) {sumWater += h;}}return sumWater;}
}
双指针
每到一个柱子都向两边遍历一遍,这其实是有重复计算的,为了得到两边的最高高度,使用了双指针来遍历。把每一个位置的左边最高高度记录在一个数组上(maxLeft),右边最高高度记录在一个数组上(maxRight),这样就避免了重复计算。
当前位置,左边的最高高度是前一个位置的左边最高高度和本高度的最大值。当前位置,右边的最高高度是前一个位置的右边最高高度和本高度的最大值。
public class Solution {public int trap(int[] height) {// 每到一个柱子都向两边遍历一遍,这其实是有重复计算// 把每一个位置的左边最高高度记录在一个数组上(maxLeft),右边最高高度记录在一个数组上(maxRight)int[] maxLeft = new int[height.length];int[] maxRight = new int[height.length];// 记录每个柱子左边柱子最大高度maxLeft[0] = height[0];for (int i = 1; i < height.length; i++) {//当前位置,左边的最高高度是前一个位置的左边最高高度和本高度的最大值maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);}// 记录每个柱子右边柱子最大高度maxRight[height.length - 1] = height[height.length - 1];for (int i = height.length - 2; i >= 0; i--) {//当前位置,右边的最高高度是前一个位置的右边最高高度和本高度的最大值maxRight[i] = Math.max(height[i], maxRight[i + 1]);}// 求和int sumWater = 0;for (int i = 0; i < height.length; i++) {// 第一个柱子和最后一个柱子不接雨水if (i==0 || i== height.length - 1) {continue;}int h = Math.min(maxLeft[i], maxRight[i]) - height[i];if (h > 0) {sumWater += h;}}return sumWater;}
}
单调栈
单调栈是按照行方向来计算雨水。
栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。因为一旦发现添加的柱子高度大于栈头元素了,此时就出现凹槽了,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子。
遇到相同高度的柱子:要求宽度的时候 如果遇到相同高度的柱子,需要使用最右边的柱子来计算宽度。
import java.util.Stack;public class Solution {public int trap(int[] height){int sumWater = 0;if (height.length <= 2) {return 0;}Stack<Integer> stack = new Stack<>();stack.push(0);for (int index = 1; index < height.length; index++){//情况一if (height[index] < height[stack.peek()]){stack.push(index);}//情况二else if (height[index] == height[stack.peek()]){// 因为相等的相邻墙,左边一个是不可能存放雨水的,所以pop左边的index, push当前的indexstack.pop();stack.push(index);}//情况三else{while (!stack.isEmpty() && (height[index] > height[stack.peek()])){int mid = stack.peek();stack.pop();if (!stack.isEmpty()){int left = stack.peek();//长就是通过柱子的高度来计算int h = Math.min(height[left], height[index]) - height[mid];//宽是通过柱子之间的下标来计算int w = index - left - 1;int area = h * w;if (area > 0) {sumWater += area;}}}stack.push(index);}}return sumWater;}
}
相关文章:
【力扣】42. 接雨水 <模拟、双指针、单调栈>
【力扣】42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 目录 【力扣】42. 接雨水题解暴力双指针单调栈 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&…...
【leetcode 力扣刷题】链表基础知识 基础操作
链表基础知识 基础操作 链表基础操作链表基础知识插入节点删除节点查找节点 707. 设计链表实现:单向链表:实现:双向链表 链表基础操作 链表基础知识 在数据结构的学习过程中,我们知道线性表【一种数据组织、在内存中存储的形式】…...
关于openfeign调用时content-type的问题
问题1描述: 今天在A服务使用openfeign调用B服务的时候,发现经常会偶发性报错。错误如下: 情况为偶发,很让人头疼。 两个接口如下: A服务接口: delayReasonApi.test(student);就是使用openfeign调用B服务的…...
OpenCV 玩转图像和视频
为什么学OpenCV? • OpenCV ⽀持对图像缩放、旋转、绘制⽂字图形等基础操作 • OpenCV 库包含了很多计算机视觉领域常⻅算法:⽬标检测、⽬标跟踪等 OpenCV 简介 • OpenCV (Open Source Computer Vision) 是计算机视觉和机器学习软件库 • Intel 1999…...
技术分享 | 如何编写同时兼容 Vue2 和 Vue3 的代码?
LigaAI 的评论编辑器、附件展示以及富文本编辑器都支持在 Vue2(Web)与 Vue3(VSCode、lDEA)中使用。这样不仅可以在不同 Vue 版本的工程中间共享代码,还能为后续升级 Vue3 减少一定阻碍。 那么,同时兼容 Vue…...
基于ArcGis提取道路中心线
基于ArcGis提取道路中心线 文章目录 基于ArcGis提取道路中心线前言一、生成缓冲区二、导出栅格数据三、导入栅格数据四、新建中心线要素五、生成中心线总结 前言 最近遇到一个问题,根据道路SHP数据生成模型的时候由于下载的道路数据杂项数据很多,所以导…...
xcode14.3更新一系列问题
1. Missing file libarclite_iphoneos.a (Xcode 14.3) 解决方法 Xcode升级到14.3后编译失败,完整错误日志: File not found: /Applications/Xcode-beta.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/arc/libarclite_iphoneo…...
1U和2U的服务器怎么选择
企业建设网站的过程中,离不开租用服务器的环节,服务器在多种场景里面都可以发挥作用,服务器租用渠道有哪些?1U、2U选哪种服务器比较好?大家跟着壹基比小鑫一起来了解具体内容吧! 1U、2U选哪种服务器比较好&…...
【SA8295P 源码分析】05 - SA8295P QNX Host 上电开机过程 进一步梳理(结合代码)
【SA8295P 源码分析】05 - SA8295P QNX Host 上电开机过程 进一步梳理(结合代码) 一、APPS PBL(Application Primary Boot Loader):固化在CPU ROM中1.1 APPS PBL 加载 XBL Loader1.2 XBL Loader加载验证并运行SMSS进行自检,自检完成后触发Warm Reset1.3 WarmRest后,APPS…...
【数据结构与算法】迪杰斯特拉算法
迪杰斯特拉算法 介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。它的主要特点是以中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。 算法过程 设置…...
python爬虫-网页数据提取
import requests #headers 网页右键->Network->最下面的User-Agent复制。 headers {"user-agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36"} #你想要的网址 url &q…...
ZigBee的Many-to-One和Source Routing
1. Many-to-One Routing Many-to-One Routing,是一种简单的路由机制,使得整个网络中的路由设备拥有回到中心节点的路由。 在这种机制下,中心节点周期性发送Many-to-One route discovery广播(协议栈默认设置为60s,可以…...
七夕节 Chinese Valentine‘s Day 的由来
农历七月初七是七夕节。Qixi Festival falls on the seventh day of the seventh lunar month. 以前有一个牛郎,和他的哥哥和嫂子住在一起。他放的一头牛曾经是天庭的一个神仙,但他违反天庭的戒律,变成牛放到了人间。As the story goes,once …...
掌握JDK21全新结构化并发编程,轻松提升开发效率!
1 概要 通过引入结构化并发编程的API,简化并发编程。结构化并发将在不同线程中运行的相关任务组视为单个工作单元,从而简化错误处理和取消操作,提高可靠性,并增强可观察性。这是一个预览版的API。 2 历史 结构化并发是由JEP 42…...
【SA8295P 源码分析】00 - 系列文章链接汇总 - 持续更新中
【SA8295P 源码分析】00 - 系列文章链接汇总 - 持续更新中 一、分区、下载、GPIO等杂项相关二、开机启动流程代码分析二、OpenWFD 显示屏模块三、Touch Panel 触摸屏模块四、QUPv3 及 QNX Host透传配置五、Camera 摄像头模块(当前正在更新中...)六、网络…...
TCP拥塞控制详解 | 6. 主动队列管理
网络传输问题本质上是对网络资源的共享和复用问题,因此拥塞控制是网络工程领域的核心问题之一,并且随着互联网和数据中心流量的爆炸式增长,相关算法和机制出现了很多创新,本系列是免费电子书《TCP Congestion Control: A Systems …...
前端学习清单
顺序不分先后。 技术名称技术描述技术链接HTML5HTML5是下一代的HTML标准,是一种用于结构化内容的标记语言。MDN|HTMLCSS3CSS3是CSS技术的升级版本,它的最大好处就是可以让网页设计师更加方便的为网页添加各种各样的样式,而不用再局限于文字、…...
go atomic原子操作详细解读
文章目录 概要1、基本知识1.1 原子操作是什么1.2 CPU怎么实现原子操作的? 2、atomic包2.1、 Add函数2.2、CompareAndSwap函数2.3、Swap函数2.4、Load函数2.5、Store函数 3、atomic.Value值 概要 atomic包是golang通过对底层系统支持的原子操作进行封装,…...
Vue用JSEncrypt对长文本json加密以及发现解密失败
哈喽 大家好啊,最近发现进行加密后 超长文本后端解密失败,经过看其他博主修改 JSEncrypt原生代码如下: // 分段加密,支持中文JSEncrypt.prototype.encryptUnicodeLong function (string) {var k this.getKey();//根据key所能编…...
Excel/PowerPoint折线图从Y轴开始(两侧不留空隙)
默认Excel/PowerPoint折线图是这个样子的: 左右两侧都留了大块空白,很难看 解决方案 点击横坐标,双击,然后按下图顺序点击 效果...
C++的类成员对齐
这是个小语法点,之前我们的对齐方式都是使用#pragma pack,这个方式实际是依赖编译器,且粒度粗(如果#pragma pack(1)之后没有#pragma pack(),那就作用整个进程了)。在C11之后引入关键字alignas,以此来实现对齐更加便利,…...
敏感挂载userhelper容器逃逸复现
目录 前言 分析 实验 前言 分析 实验 # Creates a payload cat "#!/bin/sh" > /evil-helper cat "ps > /output" >> /evil-helper chmod x /evil-helper # Finds path of OverlayFS mount for container # Unless the configuration ex…...
深度解读Promise.prototype.finally
由一个问题引发的血案: 手写源码实现Promise.prototype.finally。 我们知道,对于promise来讲,当状态敲定,无论状态兑现或拒绝时都需要调用的函数,可以使用Promise.prototype.finally的回调来实现。那么如何手写实现Pro…...
如何实现24/7客户服务自动化?建设智能客服知识库
客户自助服务是指用户通过企业或者第三方建立的网络平台或者终端,实现相关的自定义处理。实现客户服务自动化,对提高客户满意度、维持客户关系至关重要。客户服务自动化可以帮助企业以更快的速度和更高的效率来满足客户的售后服务要求,以进一…...
和鲸 ModelWhale 与中科可控多款服务器完成适配认证,赋能中国云生态
当前世界正处于新一轮技术革命及传统产业数字化转型的关键期,云计算作为重要的技术底座,其产业发展与产业规模对我国数字经济的高质量运行有着不可取代的推动作用。而随着我国数字上云、企业上云加快进入常规化阶段,云计算承载的业务应用越来…...
selenium +Jmeter 的性能测试
通过Jmeter快速将已有的Selenium 代码以性能测试的方式组织起来,并使用JMeter 丰富的报表展示测试结果 from selenium import webdriver from selenium.webdriver.common.action_chains import ActionChains from selenium.webdriver.common.by import By driver …...
探索高效的HTTP异步接口测试方法:从轮询等待到自动化方案
本文将深入探讨HTTP异步接口测试的多个方面,包括轮询等待、性能测试以及自动化方案。通过详细的解释和实际案例,帮助您了解如何有效地测试异步接口,确保系统的稳定性和性能。 在现代软件开发中,HTTP异步接口扮演着至关重要的角色&…...
Android资深工程书之LiveData核心组件原理剖析
LiveData是Android架构组件库中的一个类,用于在应用程序组件之间共享数据。它是一种可观察的数据持有者,可以感知应用程序组件的生命周期,并在数据发生变化时通知观察者。 使用LiveData 在Android应用程序中使用LiveData,你可以…...
Vue的五种方法实现加减乘除运算
五种方法的详细说明: 计算属性(Computed Properties): 计算属性是Vue.js提供的一种便捷的属性,它根据依赖的数据动态计算出一个新的值。计算属性的值会被缓存,只有当依赖的数据发生变化时,才会…...
C++(1)Linux基础知识
经济下行,计算机就业形势严峻,为了勉励自己继续进步,继续学习代码提高核心竞争力。 安装QT Creator 首先,安装QT开发工具QT Creator 参考:2021最新Qt6开发环境(Qt Creator)安装以及卸载记录_q…...
接口自动化yaml文件读取与写入
前言 在走进yaml文件之前大家应该都很想知道他是用来干嘛的? 是的是的,他是用来做接口自动化测试的。 我们一起来学习他吧!——(一定要收藏带走哦❤) 1、yaml文件有什么作用呢? ①可作为配置文件使用—…...
Java Map、JSONObject、实体类互转
文章目录 前言Map、JSONObject、实体类互转 前言 使用库 com.alibaba.fastjson2,可完成大部分JSON转换操作。 详情参考文章: Java FASTJSON2 一个性能极致并且简单易用的JSON库 Map、JSONObject、实体类互转 import com.alibaba.fastjson2.JSON; import com.alib…...
在Hive/Spark上执行TPC-DS基准测试 (PARQUET格式)
在上一篇文章:《在Hive/Spark上运行执行TPC-DS基准测试 (ORC和TEXT格式)》中,我们介绍了如何使用 hive-testbench 在Hive/Spark上执行TPC-DS基准测试,同时也指出了该项目不支持parquet格式。 如果我们想要生成parquet格式的测试数据,就需要使用其他工具了。本文选择使用另…...
基于CentOS搭建私有仓库harbor
环境: 操作系统:CentOS Linux 7 (Core) 内核: Linux 3.10.0-1160.el7.x86_64 目录 安装搭建harbor (1)安装docker编排工具docker compose (2)下载Harbor 安装包 (3&…...
PDF怎么转Word?8 个最佳 PDF 转 Word 转换器
PDF 转 Word 转换工具只是一个特殊程序,可以将 PDF(本机和/或扫描)转换为 Microsoft Office Word 格式。将 PDF 导出到 Word 的主要原因之一是满足可编辑文档的需求,尽管还有其他原因。 由于缺少 PDF 阅读器,您可以选…...
老板都爱看的财务数据分析报表,全在这了
老板们都爱看哪些财务数据分析报表?自然是可以帮助他们更好地了解公司的财务状况和经营绩效的那一类财务数据分析报表,比如利润表、资产负债表、现金流量表、应收账款分析报表、应付账款分析报表、库存分析报表等。奥威BI数据可视化工具有一套标准化财务…...
ZooKeeper(zk)与 Eureka 的区别及集群模式比较分析
作者:zhaokk 推荐阅读 AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮AI想象空间 资源分享 「java、python面试题」来自UC网盘app分享,打开手机appÿ…...
搜狗拼音占用了VSCode及微信小程序开发者工具快捷键Ctrl + Shit + K 搜狗拼音截图快捷键
修改搜狗拼音的快捷键 右键--更多设置--属性设置--按键--系统功能快捷键--系统功能快捷键设置--取消Ctrl Shit K的勾选--勾选截屏并设置为Ctrl Shit A 微信开发者工具设置快捷键 右键--Command Palette--删除行 微信开发者工具快捷键 删除行:Ctrl Shit K 或…...
PMI-ACP值得考吗?在中国的前景如何?
相信很多小伙伴都听过PMP证书吧,但是对于PMI-ACP则知之甚少。那么同为项目管理证书,PMI-ACP认证的含金量怎么样呢?今天咱们就来聊一聊PMI-ACP敏捷项目管理证书。 PMI-ACP是由PMI(美国项目管理协会)颁发的针对敏捷项目…...
centos 安装防火墙,并开启对应端口号
1.查看防火墙状态: 命令:systemctl status firewalld.service 开启防火墙时,提示没有安装防火墙 [rootlocalhost ~]# systemctl start firewalld.service Failed to start firewalld.service: Unit not found.2.安装防火墙 [rootlocalhost …...
学习微信小程序时间延迟setTimeout和setInterval的使用方法
学习微信小程序时间延迟setTimeout和setInterval的使用方法 setTimeout()setInterval() setTimeout() setTimeout在使用的时候可以实现代码块延迟执行的效果,并且可以设置延迟执行的具体时间。请见如下代码: setTimeout(function() {//要实现延迟执行效…...
Vite好用的前端构建工具
是什么 Vite是Vue的作者尤雨溪开发的 一种新型前端构建工具。 Vite在大型项目开发模式下,打包速度远高于webpack。 Vite 为什么这么快 1. 快速冷启动 Vite只启动一台静态页面的服务器,不会打包全部项目文件代码,服务器根据客户端的请求加…...
Agile Iteration Velocity
【agile iteration velocity】敏捷速度指的平均速度 第四次迭代结束速度: 76 / 4 19 第五次迭代结束速度: (76 24 ) / 5 100 / 5 20...
HarmonyOS/OpenHarmony应用开发-ArkTS语言渲染控制LazyForEach数据懒加载
LazyForEach从提供的数据源中按需迭代数据,并在每次迭代过程中创建相应的组件。当LazyForEach在滚动容器中使用了,框架会根据滚动容器可视区域按需创建组件,当组件划出可视区域外时,框架会进行组件销毁回收以降低内存占用。一、接…...
04_15页表缓存(TLB)和巨型页
前言 linux里面每个物理内存(RAM)页的一般大小都是4kb(32位就是4kb),为了使管理虚拟地址数变少 加快从虚拟地址到物理地址的映射 建议配值并使用HugePage巨型页特性 cpu和mmu和页表缓存(TLB)和cache和ram的关系 CPU看到的都是虚拟地址,需要经过MMU的转化…...
ResourceBundle类:读取配置文件
ResourceBundle类是java自带的类,类路径:java.util.ResourceBundle,用来读取项目中后缀为properties的配置文件。 下面简单举例说明一下用法: 数据准备 1)配置文件名称:application.propertiesÿ…...
数学建模的三大模型和十大常用算法
一、三大模型 预测模型 神经网络预测、灰色预测、拟合插值预测(线性回归)、时间序列预测、马尔科夫链预测、微分方程预测、Logistic模型等等。 应用领域:人口预测、水资源污染增长预测、病毒蔓延预测、竞赛获胜概率预测、月收入预测、销量预测、经济发展情况预测等在…...
NAS绝对安全吗?文件会不会泄露或被删除?
NAS(Network Attached Storage)并非绝对安全,因为任何系统都存在潜在的风险和漏洞。以下是一些可能导致文件泄露或被删除的情况: 1. 物理安全:如果未采取适当的物理安全措施,例如未将NAS设备放置在安全环境…...
Kubernetes 使用 Rancher 管理
K8S集群管理工具 只能管理单个K8S集群 kubectl命令行管理工具 dashboard(K8S官方的UI界面图形化管理工具) (管理多集群很麻烦,切换不同集群每次需要更改kube-config文件[kubectl配置文件],如果kubeadm部署每次都需…...
5G随身wifi如何选择?简单分类一下
最近5g随身wifi越来越多了,价格也一直走低,根据我的观察和总结,5g随身wifi可以分为这几档:(普遍来说) 1,紫光udx710基带芯片(也叫v510) 代表产品:r106&#x…...