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

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...