当前位置: 首页 > news >正文

【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[下标]就可以获得下标处高度:

  1. height[栈顶下标]>height[当前下标]时,将当前下标压入栈中(此时是后面的高度<前面的高度);
  2. height[栈顶下标]==height[当前下标]时,弹出栈顶下标,压入当前下标,虽然不弹出就压入也不影响计算,但是因为相同高度没法存水,可以通过这个操作避免重复计算
  3. 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 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数…...

深⼊理解指针(5)[回调函数、qsort相关知识(qsort可用于各种类型变量的排序)】

目录 1. 回调函数 2. qsort相关知识&#xff08;qsort可用于各种类型变量的排序&#xff09; 一 回调函数 1定义/作用:把函数的指针&#xff08;地址&#xff09;作为参数传递给另⼀个函数&#xff0c;当这个指针被⽤来调⽤其所指向的函数 时&#xff0c;被调⽤的函数就…...

qt QRunnable 与 QThreadPool详解

1. 概述 QRunnable是所有runnable对象的基类&#xff0c;它表示一个任务或要执行的代码。开发者需要子类化QRunnable并重写其run()函数来实现具体的任务逻辑。而QThreadPool则是一个管理QThread集合的类&#xff0c;它帮助减少创建线程的成本&#xff0c;通过管理和循环使用单…...

博客摘录「 java三年工作经验面试题整理《精华》」2023年6月12日

JDK 和 JRE 有什么区别&#xff1f;JDK&#xff1a;java 开发工具包&#xff0c;提供了 java 的开发环境和运行环境。JRE&#xff1a;java 运行环境&#xff0c;为 java 的运行提供了所需环境。JDK 其实包含了 JRE&#xff0c;同时还包含了编译 java 源码的编译器 javac&#x…...

福禄克FLUKE5500A与fluke5520a校准仪的区别功能

FLUKE5500A是美国福禄克公司的一款高性能的多功能校准仪&#xff0c;能够对手持式和台式多用表、示波器、示波表、功率计、电子温度表、数据采集器、功率谐波分析仪、进程校准器等多种仪器进行校准。 FLUKE5500A多功能校准仪供给了GPIB&#xff08;IEEE-488&#xff09;、RS-2…...

量化交易系统开发-实时行情自动化交易-2.技术栈

2019年创业做过一年的量化交易但没有成功&#xff0c;作为交易系统的开发人员积累了一些经验&#xff0c;最近想重新研究交易系统&#xff0c;一边整理一边写出来一些思考供大家参考&#xff0c;也希望跟做量化的朋友有更多的交流和合作。 本篇谈谈系统主要可以选择的技术栈&a…...

【逆向爬虫实战】--全方位分析+某某学堂登录(DES加密)

&#x1f935;‍♂️ 个人主页&#xff1a;rain雨雨编程 &#x1f604;微信公众号&#xff1a;rain雨雨编程 ✍&#x1f3fb;作者简介&#xff1a;持续分享机器学习&#xff0c;爬虫&#xff0c;数据分析 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01; …...

第2关:装载问题 (最优队列法)

问题描述 任务描述 相关知识 编程要求 测试说明 问题描述 有一批共个集装箱要装上 2 艘载重量分别为 C1 和 C2 的轮船&#xff0c;其中集 装箱i的重量为 Wi &#xff0c;且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船。如果有&#xff0c;找出一种…...

萤石设备视频接入平台EasyCVR海康私有化视频平台监控硬盘和普通硬盘有何区别?

在现代安防监控领域&#xff0c;对于数据存储和视频处理的需求日益增长&#xff0c;特别是在需要长时间、高稳定性监控的环境中&#xff0c;选择合适的存储设备和监控系统显得尤为重要。本文将深入探讨监控硬盘与普通硬盘的区别&#xff0c;并详细介绍海康私有化视频平台EasyCV…...

【Webpack配置全解析】打造你的专属构建流程️(4)

webpack 提供的 CLI 支持很多参数&#xff0c;例如 --mode&#xff0c;但更多的时候&#xff0c;我们会使用更加灵活的配置文件来控制 webpack 的行为。默认情况下&#xff0c;webpack 会读取 webpack.config.js 文件作为配置文件&#xff0c;但也可以通过 CLI 参数 --config 来…...

【SpringMVC】基础入门(1)

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;什么是Spring Web MVC 1&#xff1a;Servlet 2&#xff1a;总结 二&#xff1a;MVC …...

FFmpeg存放压缩后的音视频数据的结构体:AVPacket简介,结构体,函数

如下图的解码流程&#xff0c;AVPacket中的位置 FFmpeg源码中通过AVPacket存储压缩后的音视频数据。它通常由解复用器&#xff08;demuxers&#xff09;输出&#xff0c;然后作为输入传递给解码器。 或者从编码器作为输出接收&#xff0c;然后传递给多路复用器&#xff08;mux…...

用接地气的例子趣谈 WWDC 24 全新的 Swift Testing 入门(三)

概述 从 WWDC 24 开始&#xff0c;苹果推出了全新的测试机制&#xff1a;Swift Testing。利用它我们可以大幅度简化之前“老态龙钟”的 XCTest 编码范式&#xff0c;并且使得单元测试更加灵动自由&#xff0c;更符合 Swift 语言的优雅品味。 在这里我们会和大家一起初涉并领略…...

#渗透测试#SRC漏洞挖掘#深入挖掘CSRF漏洞02

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…...

基于OpenCV的相机捕捉视频进行人脸检测--米尔NXP i.MX93开发板

本篇测评由优秀测评者“eefocus_3914144”提供。 本文将介绍基于米尔电子MYD-LMX93开发板&#xff08;米尔基于NXP i.MX93开发板&#xff09;的基于OpenCV的人脸检测方案测试。 OpenCV提供了一个非常简单的接口&#xff0c;用于相机捕捉一个视频(我用的电脑内置摄像头) 1、安…...

【Node-Red】使用文件或相机拍摄实现图像识别

使用相机拍照实现图像识别 首先需要下载节点 node-red-contrib-tfjs-coco-ssd&#xff0c;下载不上的朋友可以根据【Node-Red】最新版coco-ssd 1.0.6安装方法&#xff08;windows&#xff09;文章进行安装。 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】特殊年份

题目描述&#xff1a; 今年是 2021 年&#xff0c;2021 这个数字非常特殊, 它的千位和十位相等, 个位比百位大 1&#xff0c;我们称满足这样条件的年份为特殊年份。 输入 5 个年份&#xff0c;请计算这里面有多少个特殊年份。 输入格式 输入 5 行&#xff0c;每行一个 4 位十…...

【云原生开发】namespace管理的后端开发设计与实现

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

威联通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设…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...