leetcode-42. 接雨水 单调栈
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 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 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5] 输出:9
提示:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
// 接雨水问题解决方案类
class Solution {
public:/*** 计算给定高度图下雨后能接多少雨水* @param height 一系列非负整数表示的高度图* @return 返回能接的雨水总量*/int trap(vector<int>& height) {// 总水量int sum = 0;// 高度图长度int len = height.size();// 使用栈来存储高度和对应索引stack<int> hv;stack<int> hi;// 初始化栈,将第一个高度和索引入栈hv.push(height[0]);hi.push(0);// 遍历高度图for(int i = 1; i < len; i++){// 当前高度小于栈顶高度,直接入栈if(height[i]<hv.top()){hv.push(height[i]);hi.push(i);}// 当前高度等于栈顶高度,更新栈顶else if(height[i]==hv.top()){hv.pop();hi.pop();hv.push(height[i]);hi.push(i);}// 当前高度大于栈顶高度,开始结算水量else{// 当栈不为空且当前高度大于栈顶高度时,循环结算水量while(!hv.empty()&& height[i] > hv.top()){// 弹出栈顶,计算被夹在中间的雨水int mid =hi.top();hi.pop();hv.pop();// 如果栈不为空,说明还有边界高度可以形成容器if(!hv.empty()){// 计算容器的高度差int h = min(hv.top(), height[i]) - height[mid];// 计算容器的宽度int w =i -hi.top()-1;// 累加水量sum +=h*w;}}// 当前高度入栈hv.push(height[i]);hi.push(i);}}// 返回总水量return sum;}
};
相关文章:
leetcode-42. 接雨水 单调栈
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 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] 表…...
ThinkPHP和PHP的区别
文章目录 ThinkPHP和PHP的区别一、引言二、PHP简介1、第一步1.1、示例代码 三、ThinkPHP简介2、第二步2.1、特点2.2、示例代码 四、总结 ThinkPHP和PHP的区别 一、引言 在Web开发领域,PHP是一种广泛使用的开源脚本语言,而ThinkPHP则是一个基于PHP的MVC…...
clientWidth,offsetWidth,scrollHeight
clientWidth: offsetWidth: scrollHeight:...
SVN版本回退
SVN 版本回退三种方法: Update item to this version 假设我们的项目文件一共有8个版本,它版本号分别是1,2,3,4,5,6,7,8。 这个选项的作用是将文件版本更新到对应所选的…...
IDEA关联Tomcat
一、Tomcat服务器 web服务器,就是运行web项目的容器 即运行java代码的一个容器 webapp(web应用程序) --> 就是我们写的javaweb项目 Tomcat 是Apache 软件基金会(Apache Software Foundation)下的一个核心项目,免费开源、并支持Servlet 和J…...
MongoDB mongoose 的 save、insert 和 create 方法的比较
目录 save 方法 insert 方法 create 方法 使用会话和事务 总结 在本文中,我们将介绍 MongoDB 中使用 mongoose 操作 数据库时的三种常见方法:save、insert 和 create。这些方法可以用于将数据存储到 MongoDB 数据库中,并且在一定程度上具…...
Maven安装使用
说明:Maven是Apache旗下的一个开源项目,是一款用于管理和构建java项目的工具。一般来说,它帮助我们管理依赖、构建项目。本文介绍在Windows系统下安装Maven。 下载&安装&验证 下载 首先,在Maven官网(https:…...
微信第三方开放平台接入本地消息事件接口报错问题java.security.InvalidKeyException: Illegal key size
先看报错: java.security.InvalidKeyException: Illegal key sizeat javax.crypto.Cipher.checkCryptoPerm(Cipher.java:1039)at javax.crypto.Cipher.implInit(Cipher.java:805)at javax.crypto.Cipher.chooseProvider(Cipher.java:864)at javax.crypto.Cipher.in…...
如何只修改obsidian图片链接为markdown
如何只修改obsidian图片链接为markdown 前言插件配置 使用注意 前言 适合有一定了解obsidian用法和插件市场,还有相对路径的人 插件 在obsidian插件市场搜索—开梯子 配置 首先使用ctrlp打开命令面板,也可以在左侧通过图标打开命令面板,…...
AI不可尽信
看到某项目有类似这样的一段代码 leaves : make([]int, 10) leaves leaves[:0]没理解这样的连续两行,有何作用? 初始化一个长度和容量都为10的切片,接着把切片长度设置为0 即如下demo: (在线地址) package mainimport "fmt"func main() {leaves : make([]int, 1…...
[C++]使用纯opencv部署yolov11旋转框目标检测
【官方框架地址】 GitHub - ultralytics/ultralytics: Ultralytics YOLO11 🚀 【算法介绍】 YOLOv11是一种先进的对象检测算法,它通过单个神经网络实现了快速的物体检测。其中,旋转框检测是YOLOv11的一项重要特性,它可以有效地检…...
Python入门--函数
目录 1. 函数介绍 2. 函数的定义 3. 函数的参数 4. 函数的返回值 5. 函数说明文档 6. 函数的嵌套调用 7. 函数的作用域 (1). 局部变量 (2). 全局变量 (3). global关键字 1. 函数介绍 函数:是组织好的,可重复使用的,用来实现特定功能…...
winFrom界面无法打开
🏆本文收录于《全栈Bug调优(实战版)》专栏,主要记录项目实战过程中所遇到的Bug或因后果及提供真实有效的解决方案,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&am…...
【Linux】Ubuntu20.04上使用RabbitVCS的图形化SVN
文章目录 1、RabbitVCS1.1、RabbitVCS 介绍1.2、RabbitVCS 主要功能1.3、Ubuntu下 TortoiseSVN 替代者 2、安装2.1、命令安装2.2、安装使用2.3、使用权限 3、解决SVN无法保存密码问题3.1、问题描述3.2、解决方法 1、RabbitVCS 1.1、RabbitVCS 介绍 它是一款Linux系统下的图形…...
DMA直接存储器存取
参考视频:[8-1] DMA直接存储器存取_哔哩哔哩_bilibili DMA简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设和存储器或者存储器和存储器之间的高速数据传输,无须CPU干预,节省了CPU的资源 12个独立可…...
java计算机毕设课设—坦克大战游戏
这是什么系统? 坦克大战游戏是一款以坦克为主题的射击游戏,旨在为玩家提供一个刺激、有趣的游戏体验。该游戏不仅拥有丰富的功能,还注重玩家的互动体验。此系统是使用Java语言实现坦克大战游戏程序,玩家通过连接访问进入游戏&…...
Vue入门-指令学习-v-on
v-on 作用:注册事件 添加监听 提供处理逻辑 语法: v-on:事件名"内联语句" v-on:事件名"methods中的函数名" 注意:" v-on:"可以替换为" " v-on:click"XXX" --> cli…...
Maven的生命周期与依赖作用域介绍
说明:本文介绍Maven的生命周期,以及在pom.xml文件中每个依赖(dependency标签内)scope标签的内容。 Maven生命周期 在IDEA项目中,右侧边栏,点Maven,可以看到以下生命周期。 其中, c…...
Django学习笔记四:urls配置详解
Django是一个高级的Python Web框架,它鼓励快速开发和干净、实用的设计。URL配置是Django框架中非常重要的一部分,它定义了URL模式与视图函数之间的映射关系。以下是Django URL配置的详解: URL配置文件 通常,URL配置位于Django项…...
NIO的callback调用方式
1.消费者 public class CallbackClient {public static void main(String[] args) {try {SocketChannel socketChannel SocketChannel.open();socketChannel.connect(new InetSocketAddress("127.0.0.1", 8000));ByteBuffer writeBuffer ByteBuffer.allocate(32);…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
