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

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...