【LeetCode】【算法】42. 接雨水
LeetCode 42. 接雨水
题目描述
给定 n 个非负整数表示每个宽度为 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 个单位的雨水(蓝色部分表示雨水)。
思路
单调栈
首先考虑清楚存储雨水的必要条件是:后面的高度>前面的高度才有可能做雨水存储,所以这里最好可以用单调栈实现。
下面的单调栈中存储输入数组的下标,通过height[下标]就可以获得下标处高度:
- 当
height[栈顶下标]>height[当前下标]时,将当前下标压入栈中(此时是后面的高度<前面的高度); - 当
height[栈顶下标]==height[当前下标]时,弹出栈顶下标,压入当前下标,虽然不弹出就压入也不影响计算,但是因为相同高度没法存水,可以通过这个操作避免重复计算 - 当
height[栈顶下标]<height[当前下标]时,就到了计算存水面积的时候了,这里需要不断弹出那些小的元素。那么,储水高度height=Math.min(height[栈顶下标的left],height[栈顶下标的right])-height[栈顶下标],就相当于把栈顶的高度作为底,左右围在一起形成一个容器。储水宽度width=栈顶下标的right-栈顶下标的left-1。最终面积sum+=h*w。
代码
class Solution {public int trap(int[] height) {// 根据卡神单调栈版写的int size = height.length;if (size <= 2) return 0; // 接不到雨水直接returnStack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int i = 1; i < height.length; i++) {int stackTop = stack.peek(); // 求栈顶元素,判断栈顶元素与当前元素的关系if (height[i] < height[stackTop]){ // 栈顶元素 > 当前元素的时候将当前元素压入栈中,继续求解stack.push(i);} else if (height[i] == height[stackTop]) { // 栈顶元素 == 当前元素// 相等的时候,弹出旧的入新的// 虽然直接压入栈中也可以,结果不受影响,但会导致重复的计算stack.pop();stack.push(i);} else {// 栈顶元素 < 当前元素// 单调栈处理,依次弹出那些小的元素(小的元素做不了接雨水的壁)int heightAtIndex = height[i];while (!stack.isEmpty() && heightAtIndex > height[stackTop]){int mid = stack.pop();if (!stack.isEmpty()){int left = stack.peek();int h = Math.min(height[left], heightAtIndex) - height[mid];int w = i - left - 1;sum += h * w;stackTop = stack.peek();}}stack.push(i);}}return sum;}
}
相关文章:
【LeetCode】【算法】42. 接雨水
LeetCode 42. 接雨水 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数…...
深⼊理解指针(5)[回调函数、qsort相关知识(qsort可用于各种类型变量的排序)】
目录 1. 回调函数 2. qsort相关知识(qsort可用于各种类型变量的排序) 一 回调函数 1定义/作用:把函数的指针(地址)作为参数传递给另⼀个函数,当这个指针被⽤来调⽤其所指向的函数 时,被调⽤的函数就…...
qt QRunnable 与 QThreadPool详解
1. 概述 QRunnable是所有runnable对象的基类,它表示一个任务或要执行的代码。开发者需要子类化QRunnable并重写其run()函数来实现具体的任务逻辑。而QThreadPool则是一个管理QThread集合的类,它帮助减少创建线程的成本,通过管理和循环使用单…...
博客摘录「 java三年工作经验面试题整理《精华》」2023年6月12日
JDK 和 JRE 有什么区别?JDK:java 开发工具包,提供了 java 的开发环境和运行环境。JRE:java 运行环境,为 java 的运行提供了所需环境。JDK 其实包含了 JRE,同时还包含了编译 java 源码的编译器 javac&#x…...
福禄克FLUKE5500A与fluke5520a校准仪的区别功能
FLUKE5500A是美国福禄克公司的一款高性能的多功能校准仪,能够对手持式和台式多用表、示波器、示波表、功率计、电子温度表、数据采集器、功率谐波分析仪、进程校准器等多种仪器进行校准。 FLUKE5500A多功能校准仪供给了GPIB(IEEE-488)、RS-2…...
量化交易系统开发-实时行情自动化交易-2.技术栈
2019年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 本篇谈谈系统主要可以选择的技术栈&a…...
【逆向爬虫实战】--全方位分析+某某学堂登录(DES加密)
🤵♂️ 个人主页:rain雨雨编程 😄微信公众号:rain雨雨编程 ✍🏻作者简介:持续分享机器学习,爬虫,数据分析 🐋 希望大家多多支持,我们一起进步! …...
第2关:装载问题 (最优队列法)
问题描述 任务描述 相关知识 编程要求 测试说明 问题描述 有一批共个集装箱要装上 2 艘载重量分别为 C1 和 C2 的轮船,其中集 装箱i的重量为 Wi ,且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船。如果有,找出一种…...
萤石设备视频接入平台EasyCVR海康私有化视频平台监控硬盘和普通硬盘有何区别?
在现代安防监控领域,对于数据存储和视频处理的需求日益增长,特别是在需要长时间、高稳定性监控的环境中,选择合适的存储设备和监控系统显得尤为重要。本文将深入探讨监控硬盘与普通硬盘的区别,并详细介绍海康私有化视频平台EasyCV…...
【Webpack配置全解析】打造你的专属构建流程️(4)
webpack 提供的 CLI 支持很多参数,例如 --mode,但更多的时候,我们会使用更加灵活的配置文件来控制 webpack 的行为。默认情况下,webpack 会读取 webpack.config.js 文件作为配置文件,但也可以通过 CLI 参数 --config 来…...
【SpringMVC】基础入门(1)
阿华代码,不是逆风,就是我疯 你们的点赞收藏是我前进最大的动力!! 希望本文内容能够帮助到你!! 目录 一:什么是Spring Web MVC 1:Servlet 2:总结 二:MVC …...
FFmpeg存放压缩后的音视频数据的结构体:AVPacket简介,结构体,函数
如下图的解码流程,AVPacket中的位置 FFmpeg源码中通过AVPacket存储压缩后的音视频数据。它通常由解复用器(demuxers)输出,然后作为输入传递给解码器。 或者从编码器作为输出接收,然后传递给多路复用器(mux…...
用接地气的例子趣谈 WWDC 24 全新的 Swift Testing 入门(三)
概述 从 WWDC 24 开始,苹果推出了全新的测试机制:Swift Testing。利用它我们可以大幅度简化之前“老态龙钟”的 XCTest 编码范式,并且使得单元测试更加灵动自由,更符合 Swift 语言的优雅品味。 在这里我们会和大家一起初涉并领略…...
#渗透测试#SRC漏洞挖掘#深入挖掘CSRF漏洞02
免责声明 本教程仅为合法的教学目的而准备,严禁用于任何形式的违法犯罪活动及其他商业行为,在使用本教程前,您应确保该行为符合当地的法律法规,继续阅读即表示您需自行承担所有操作的后果,如有异议,请立即停…...
基于OpenCV的相机捕捉视频进行人脸检测--米尔NXP i.MX93开发板
本篇测评由优秀测评者“eefocus_3914144”提供。 本文将介绍基于米尔电子MYD-LMX93开发板(米尔基于NXP i.MX93开发板)的基于OpenCV的人脸检测方案测试。 OpenCV提供了一个非常简单的接口,用于相机捕捉一个视频(我用的电脑内置摄像头) 1、安…...
【Node-Red】使用文件或相机拍摄实现图像识别
使用相机拍照实现图像识别 首先需要下载节点 node-red-contrib-tfjs-coco-ssd,下载不上的朋友可以根据【Node-Red】最新版coco-ssd 1.0.6安装方法(windows)文章进行安装。 1、智能识别图片 使用本地文件的形式对图像进行识别 时间戳&…...
【Arcpy】提示需要深度学习框架代码
try:import torchimport arcgis相关库HAS_DEPS True except:HAS_DEPS Falsedef _raise_conda_import_error():arcpy.AddIDMessage("ERROR", 260005)exit(260005)if not HAS_DEPS:_raise_conda_import_error()...
【蓝桥杯 2021 省 B2】特殊年份
题目描述: 今年是 2021 年,2021 这个数字非常特殊, 它的千位和十位相等, 个位比百位大 1,我们称满足这样条件的年份为特殊年份。 输入 5 个年份,请计算这里面有多少个特殊年份。 输入格式 输入 5 行,每行一个 4 位十…...
【云原生开发】namespace管理的后端开发设计与实现
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...
威联通Docker Compose搭建NAS媒体库资源工具NAS Tools
文章目录 一、环境配置1-1 需要的配件1-2 环境安装及配置注意:获取PUID/PGID1-3 目录位置准备总结,这里我们要做5件事备注:Docker无法下载解决办法二、登录配件,进行配件连接和配置2-1 jackett设置2-2 qBittorrent设置!!!设置文件下载地址2-3 jellyfin设置2-4 NASTools设…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
