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

力扣---接雨水---单调队列

题目:

单调队列思想:

没有思路的小伙伴可以先把这个想清楚哦:力扣hot10---大根堆+双端队列-CSDN博客

从上面的图就可以发现,如果柱子呈递减序列,那么不会接到雨水,只要有一个小凸起柱子,那么这个柱子就会和之前的柱子接到雨水。所以我们维护一个递减序列,如果遍历到某个柱子接到雨水时,就把前面比他矮的柱子pop掉,同时因为接到了雨水,前面的柱子高度也会发生变化,变成了接完雨水后的最高值(height数组中的元素值需改变的原因为:考虑到后面还会有更高的柱子使得该柱子再次接到点雨水,我们需要改变柱子的长度)。一个柱子能接雨水的最大值该怎么求呢?首先,我们比较遍历到的这个柱子和队列中第一高的柱子哪个更低,如果该值为lower,那么接到的雨水部分英文lower-height[ i ]。不清晰的友友直接看代码吧~

代码:

C++:

class Solution {
public:int calculate(vector<int>& height,int idx_r,int idx_l){int s=0;int min_=min(height[idx_l],height[idx_r]);int r=height[idx_r];for(int i=idx_l;i<idx_r;i++){if(r>height[i]){s+=min_-height[i];height[i]=min_;}}return s;}int trap(vector<int>& height) {//单调队列(维护递减的序列)deque<pair<int,int>> q;int len=height.size();int s=0;for(int i=0;i<len;i++){//出while(!q.empty() and q.back().first<=height[i]){s+=calculate(height,i,q.front().second); //计算新加的面积大小,同时改变数组中的元素,因为已经接了雨水q.pop_back();}//进q.push_back({height[i],i});}return s;}
};

Python:

class Solution:def calculate(self,height:List[int],idx_r:int,idx_l:int) -> int:s=0min_=min(height[idx_l],height[idx_r])r=height[idx_r]for i in range(idx_l,idx_r):if r>height[i]:s+=min_-height[i]height[i]=min_return sdef trap(self, height: List[int]) -> int:q=deque()height_len=len(height)s=0for i in range(height_len):while q and q[-1][0]<=height[i]:s+=self.calculate(height,i,q[0][1])q.pop()q.append((height[i],i))return s

明天继续更新这道题的动态规划做法以及力扣hot--课程表

相关文章:

力扣---接雨水---单调队列

题目&#xff1a; 单调队列思想&#xff1a; 没有思路的小伙伴可以先把这个想清楚哦&#xff1a;力扣hot10---大根堆双端队列-CSDN博客 从上面的图就可以发现&#xff0c;如果柱子呈递减序列&#xff0c;那么不会接到雨水&#xff0c;只要有一个小凸起柱子&#xff0c;那么这个…...

微分学<4>——微分中值定理

索引 微分中值定理极值定义4.1 极大(小)值定理4.1 Fermat引理定理4.2 Rolle定理 Lagrange中值定理定理4.3 Lagrange中值定理定理4.4 Cauchy中值定理 导数对函数性质的刻画Jensen不等式 微分中值定理 极值 定义4.1 极大(小)值 若存在 x 0 x_{0} x0​的邻域 U ( x 0 , δ ) U\…...

FPGA的时钟资源

目录 简介 Clock Region详解 MRCC和SRCC的区别 BUFGs 时钟资源总结 简介 7系列FPGA的时钟结构图&#xff1a; Clock Region&#xff1a;时钟区域&#xff0c;下图中有6个时钟区域&#xff0c;用不同的颜色加以区分出来 Clock Backbone&#xff1a;从名字也能看出来&#x…...

LeetCode27: 移除元素

题目描述 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出…...

Python使用Beautiful Soup及解析html获取元素并提取内容值

Python使用Beautiful Soup及解析html获取元素并提取内容值 1. 包括解析获取标题2. 根据标签及id获取所有元素3. 根据标签及class获取所有元素4. 获取元素下的标签的值5. 获取元素下的parent及child的元素的值参考 1. 包括解析获取标题 2. 根据标签及id获取所有元素 3. 根据标…...

如何清除keep-alive缓存

在 Vue.js 中&#xff0c;使用 <keep-alive> 组件可以将组件保留在内存中&#xff0c;以避免重复渲染和销毁&#xff0c;从而提高性能。如果需要手动清除 <keep-alive> 组件的缓存&#xff0c;可以通过两种方法来实现&#xff1a; 通过 $destroy 方法销毁组件&…...

2024年新手视频剪辑软件推荐-6款视频剪辑软件测评

视频剪辑软件推荐 premiere premiere 直达地址:各大软件网站 说到底,还是得专业的来,虽然很多人觉得他是收费的,但是你懂的,想要免费总是会有办法的.别的不说,剪辑这块,我还是很认可这个软件,虽然我现在还是刚入门. 剪映 剪映 抖音官方推出的一款手机视频编辑剪辑应用,提供切割…...

无货源抖店可以做吗?那些月入上万是真的吗?分享我的成功秘籍

大家好&#xff0c;我是电商花花。 现在还是有人在不停的在问&#xff0c;抖音小店无货源还可以做吗&#xff1f;那些月入上万都是真的吗&#xff1f; 当然是真的&#xff0c;而且做抖音小店非常简单&#xff0c;前提是你真的完全掌握到核心玩法&#xff0c;且要有执行力。 …...

文献阅读:DEA-Net:基于细节增强卷积和内容引导注意的单图像去雾

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 摘要Abstract文献阅读&#xff1a;DEA-Net&#xff1a;基于细节增强卷积和内容引导注意的单图像去雾1、研究背景2、方法提出3、相关知识3.1、DEConv3.3、多重卷积的…...

2024想要赚点小钱真的很容易!帮你们找的10个搞钱第二职业

我们都希望在空闲时间里增加一些额外收入&#xff0c;并有机会找到自己热爱的事业&#xff0c;每天贝兼几十上百元是一个不错的开始&#xff0c;小钱也是钱&#xff0c; 搞钱的经验会积少成多。今天分享10个搞钱第二职业&#xff0c;2024想要赚点小钱真的很容易。 一.摆摊卖花 …...

【Linux网络】再谈 “协议“

目录 再谈 "协议" 结构化数据的传输 序列化和反序列化 网络版计算器 封装套接字操作 服务端代码 服务进程执行例程 启动网络版服务端 协议定制 客户端代码 代码测试 使用JSON进行序列化与反序列化 我们程序员写的一个个解决我们实际问题&#xff0c;满…...

猫头虎分享已解决Bug || 系统监控故障:MonitoringServiceDown, MetricsCollectionError

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …...

Java中的基本数据类型有哪些

在Java编程语言中&#xff0c;基本数据类型&#xff08;Primitive Types&#xff09;是预定义的数据类型&#xff0c;它们不是由用户定义的类创建的&#xff0c;而是由语言本身提供的。这些基本数据类型是构成Java程序的基础&#xff0c;用于存储不同类型的值&#xff0c;如整数…...

二叉树遍历(前中后序的递归/非递归遍历、层序遍历)

二叉树的遍历 1. 二叉树的前序、中序、后序遍历 前、中、后序遍历又叫深度优先遍历 注&#xff1a;严格来说&#xff0c;深度优先遍历是先访问当前节点再继续递归访问&#xff0c;因此&#xff0c;只有前序遍历是严格意义上的深度优先遍历 首先需要知道下面几点&#xff1a; …...

UE4升级UE5 蓝图节点变更汇总(4.26/27-5.2/5.3)

一、删除部分 Ploygon Editing删除 Polygon Editing这个在4.26、4.27中的插件&#xff0c;在5.1后彻底失效。 相关的蓝图&#xff0c;如编辑器蓝图 Generate mapping UVs等&#xff0c;均失效。 如需相关功能&#xff0c;请改成Dynamic Mesh下的方法。 GetSupportedClass删…...

【python】异常处理

前言 省略各种废话&#xff0c;直接快速整理知识点 try-except 基础 作用 程序不可能永远都是对的&#xff0c;当7除a&#xff0c;a由用户输入时&#xff0c;用户输入0就会报错。try-except就是解决这些问题。 结构 多分支自定义错误类型 上方的exception是一个错误类型…...

【xv6操作系统】Lab systems calls

一、实验前须知 阅读 xv6 文档的第 2 章和第 4 章的 4.3 节和 4.4 节以及相关源文件&#xff1a; 系统调用的用户空间代码在 user/user.h 和 user/usys.pl 中。 内核空间代码在 kernel/syscall.h 和 kernel/syscall.c 中。 与进程相关的代码在 kernel/proc.h 和 kernel/proc.c…...

python的scripts文件夹作用

Windows系统&#xff1a; Scripts文件夹通常位于Python的安装目录下&#xff0c;如C:\Python\Scripts。该文件夹内包含了各种有用的工具&#xff0c;例如pip、virtualenv等&#xff0c;这些工具有助于管理和配置Python环境和依赖包。 Linux系统&#xff1a; 在Linux系统中&…...

Discuz论坛网站报错Discuz!Database Error(0)notconnect的解决办法

运营服务器大本营有段时间了&#xff0c;在运营期间遇到两次Discuz&#xff01;Database Error&#xff08;0&#xff09;notconnect报错&#xff0c;和你们分享遇到Discuz报错的解决办法&#xff0c;希望可以帮助到你。 首先网站报错&#xff08;0&#xff09;notconnect&…...

掌握mysql,看完这篇文章就够了

​数据库 对大量数据进行存储和管理&#xff08;增删改查&#xff09; 客户端&#xff1a; 黑窗口终端navicat 熊掌软件数据库分类&#xff1a; 关系型数据库 通过表与表产生关联关系&#xff0c;每个表中都存储结构化数据&#xff0c;支持sql结构化查询语言MysqlOracleSQLS…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...