当前位置: 首页 > 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设…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...