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

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.length
  • 1 <= n <= 2 * 104
  • 0 <= 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 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [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开发领域&#xff0c;PHP是一种广泛使用的开源脚本语言&#xff0c;而ThinkPHP则是一个基于PHP的MVC…...

clientWidth,offsetWidth,scrollHeight

clientWidth: offsetWidth&#xff1a; scrollHeight&#xff1a;...

SVN版本回退

SVN 版本回退三种方法&#xff1a; Update item to this version 假设我们的项目文件一共有8个版本&#xff0c;它版本号分别是1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;6&#xff0c;7&#xff0c;8。 这个选项的作用是将文件版本更新到对应所选的…...

IDEA关联Tomcat

一、Tomcat服务器 web服务器,就是运行web项目的容器 即运行java代码的一个容器 webapp(web应用程序) --> 就是我们写的javaweb项目 Tomcat 是Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;下的一个核心项目&#xff0c;免费开源、并支持Servlet 和J…...

MongoDB mongoose 的 save、insert 和 create 方法的比较

目录 save 方法 insert 方法 create 方法 使用会话和事务 总结 在本文中&#xff0c;我们将介绍 MongoDB 中使用 mongoose 操作 数据库时的三种常见方法&#xff1a;save、insert 和 create。这些方法可以用于将数据存储到 MongoDB 数据库中&#xff0c;并且在一定程度上具…...

Maven安装使用

说明&#xff1a;Maven是Apache旗下的一个开源项目&#xff0c;是一款用于管理和构建java项目的工具。一般来说&#xff0c;它帮助我们管理依赖、构建项目。本文介绍在Windows系统下安装Maven。 下载&安装&验证 下载 首先&#xff0c;在Maven官网&#xff08;https:…...

微信第三方开放平台接入本地消息事件接口报错问题java.security.InvalidKeyException: Illegal key size

先看报错&#xff1a; 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用法和插件市场&#xff0c;还有相对路径的人 插件 在obsidian插件市场搜索—开梯子 配置 首先使用ctrlp打开命令面板&#xff0c;也可以在左侧通过图标打开命令面板&#xff0c…...

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 &#x1f680; 【算法介绍】 YOLOv11是一种先进的对象检测算法&#xff0c;它通过单个神经网络实现了快速的物体检测。其中&#xff0c;旋转框检测是YOLOv11的一项重要特性&#xff0c;它可以有效地检…...

Python入门--函数

目录 1. 函数介绍 2. 函数的定义 3. 函数的参数 4. 函数的返回值 5. 函数说明文档 6. 函数的嵌套调用 7. 函数的作用域 (1). 局部变量 (2). 全局变量 (3). global关键字 1. 函数介绍 函数&#xff1a;是组织好的&#xff0c;可重复使用的&#xff0c;用来实现特定功能…...

winFrom界面无法打开

&#x1f3c6;本文收录于《全栈Bug调优(实战版)》专栏&#xff0c;主要记录项目实战过程中所遇到的Bug或因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&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直接存储器存取

参考视频&#xff1a;[8-1] DMA直接存储器存取_哔哩哔哩_bilibili DMA简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设和存储器或者存储器和存储器之间的高速数据传输&#xff0c;无须CPU干预&#xff0c;节省了CPU的资源 12个独立可…...

java计算机毕设课设—坦克大战游戏

这是什么系统&#xff1f; 坦克大战游戏是一款以坦克为主题的射击游戏&#xff0c;旨在为玩家提供一个刺激、有趣的游戏体验。该游戏不仅拥有丰富的功能&#xff0c;还注重玩家的互动体验。此系统是使用Java语言实现坦克大战游戏程序&#xff0c;玩家通过连接访问进入游戏&…...

Vue入门-指令学习-v-on

v-on 作用&#xff1a;注册事件 添加监听 提供处理逻辑 语法&#xff1a; v-on:事件名"内联语句" v-on:事件名"methods中的函数名" 注意&#xff1a;" v-on&#xff1a;"可以替换为" " v-on:click"XXX" --> cli…...

Maven的生命周期与依赖作用域介绍

说明&#xff1a;本文介绍Maven的生命周期&#xff0c;以及在pom.xml文件中每个依赖&#xff08;dependency标签内&#xff09;scope标签的内容。 Maven生命周期 在IDEA项目中&#xff0c;右侧边栏&#xff0c;点Maven&#xff0c;可以看到以下生命周期。 其中&#xff0c; c…...

Django学习笔记四:urls配置详解

Django是一个高级的Python Web框架&#xff0c;它鼓励快速开发和干净、实用的设计。URL配置是Django框架中非常重要的一部分&#xff0c;它定义了URL模式与视图函数之间的映射关系。以下是Django URL配置的详解&#xff1a; URL配置文件 通常&#xff0c;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);…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...