【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设…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
【iOS】 Block再学习
iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...
路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...
OpenGL-什么是软OpenGL/软渲染/软光栅?
软OpenGL(Software OpenGL)或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式(包括几何处理、光栅化、着色等),不依赖GPU硬件加速。这种模式通常性能较低,但兼容性极强,常用于不支持硬件加速…...
Android Framework预装traceroute执行文件到system/bin下
文章目录 Android SDK中寻找traceroute代码内置traceroute到SDK中traceroute参数说明-I 参数(使用 ICMP Echo 请求)-T 参数(使用 TCP SYN 包) 相关文章 Android SDK中寻找traceroute代码 设备使用的是Android 11,在/s…...
本地部署drawDB结合内网穿透技术实现数据库远程管控方案
文章目录 前言1. Windows本地部署DrawDB2. 安装Cpolar内网穿透3. 实现公网访问DrawDB4. 固定DrawDB公网地址 前言 在数字化浪潮席卷全球的背景下,数据治理能力正日益成为构建现代企业核心竞争力的关键因素。无论是全球500强企业的数据中枢系统,还是初创…...
