代码随想录算法训练营第五十八天丨 动态规划part18
739. 每日温度
思路
首先想到的当然是暴力解法,两层for循环,把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)
那么接下来在来看看使用单调栈的解法。
什么时候用单调栈呢?
通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
例如本题其实就是找找到一个元素右边第一个比自己大的元素,此时就应该想到用单调栈了。
那么单调栈的原理是什么呢?为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢?
单调栈的本质是空间换时间,因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素,优点是整个数组只需要遍历一次。
更直白来说,就是用一个栈来记录我们遍历过的元素,因为我们遍历数组的时候,我们不知道之前都遍历了哪些元素,以至于遍历一个元素找不到是不是之前遍历过一个更小的,所以我们需要用一个容器(这里用单调栈)来记录我们遍历过的元素。
在使用单调栈的时候首先要明确如下几点:
- 单调栈里存放的元素是什么?
单调栈里只需要存放元素的下标 i 就可以了,如果需要使用对应的元素,直接T[i]就可以获取。
- 单调栈里元素是递增呢? 还是递减呢?
注意以下讲解中,顺序的描述为 从栈头到栈底的顺序,因为单纯的说从左到右或者从前到后,不说栈头朝哪个方向的话,大家一定比较懵。
这里我们要使用递增循序(再强调一下是指从栈头到栈底的顺序),因为只有递增的时候,栈里要加入一个元素i的时候,才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
即:如果求一个元素右边第一个更大元素,单调栈就是递增的,如果求一个元素右边第一个更小元素,单调栈就是递减的。
文字描述理解起来有点费劲,接下来我画了一系列的图,来讲解单调栈的工作过程,大家再去思考,本题为什么是递增栈。
使用单调栈主要有三个判断条件。
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
把这三种情况分析清楚了,也就理解透彻了。
接下来我们用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析,输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
首先先将第一个遍历元素加入单调栈
加入T[1] = 74,因为T[1] > T[0](当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况)。
我们要保持一个递增单调栈(从栈头到栈底),所以将T[0]弹出,T[1]加入,此时result数组可以记录了,result[0] = 1,即T[0]右面第一个比T[0]大的元素是T[1]。
加入T[2],同理,T[1]弹出
加入T[3],T[3] < T[2] (当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况),加T[3]加入单调栈。
加入T[4],T[4] == T[3] (当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况),此时依然要加入栈,不用计算距离,因为我们要求的是右面第一个大于本元素的位置,而不是大于等于!
加入T[5],T[5] > T[4] (当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况),将T[4]弹出,同时计算距离,更新result
T[4]弹出之后, T[5] > T[3] (当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况),将T[3]继续弹出,同时计算距离,更新result
直到发现T[5]小于T[st.top()],终止弹出,将T[5]加入单调栈
加入T[6],同理,需要将栈里的T[5],T[2]弹出
同理,继续弹出
此时栈里只剩下了T[6]
加入T[7], T[7] < T[6] 直接入栈,这就是最后的情况,result数组也更新完了。
此时可能就疑惑了,那result[6] , result[7]怎么没更新啊,元素也一直在栈里。
其实定义result数组的时候,就应该直接初始化为0,如果result没有更新,说明这个元素右面没有更大的了,也就是为0。
以上在图解的时候,已经把,这三种情况都做了详细的分析。
- 情况一:当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 情况二:当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 情况三:当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
通过以上过程,大家可以自己再模拟一遍,就会发现:只有单调栈递增(从栈口到栈底顺序),就是求右边第一个比自己大的,单调栈递减的话,就是求右边第一个比自己小的。
代码如下:
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] answer = new int[temperatures.length];//小的话一直压栈记录,大的话就下表相减求距离/**如果当前遍历的元素 大于栈顶元素,表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素,所以弹出 栈顶元素,并记录如果栈不空的话,还要考虑新的栈顶与当前元素的大小关系否则的话,可以直接入栈。注意,单调栈里 加入的元素是 下标。*/Stack<Integer> st = new Stack<>();st.push(0);for (int i = 1; i < temperatures.length; i++) {if (temperatures[i] > temperatures[st.peek()]){//如果当前元素大于栈顶元素//遍历栈,如果碰到当前元素小于等于栈顶元素时,将当前元素的下标放入栈中//如果当前元素大于栈顶元素,栈顶元素为下标的值为 i- st.popwhile (!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){if (temperatures[i] > temperatures[st.peek()]){int stIndex = st.pop();answer[stIndex] = i - stIndex;}}st.push(i);}else {//当前元素小于等于栈顶元素st.push(i);}}return answer;}
}
496.下一个更大元素 I
思路
这题秒了基本没看卡哥的题解,但思路基本也是与卡哥的一致。但需要注意的细节点是,每次 i 遍历完之后需要对栈stack 进行清空处理,防止本次遗留元素影响到下一次层的循环中。
并且我将结果数组 res[] 均初始化为了-1,具体思路见代码:
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {//nums1 是 nums2 的子集int[] res = new int[nums1.length];Arrays.fill(res,-1);Stack<Integer> st = new Stack<>();//找出num1[i] == num2[j]的j 值for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {if (nums1[i] == nums2[j]){//确定 nums2[j] 的 下一个更大元素st.push(j);}if (!st.isEmpty() && nums2[j] > nums2[st.peek()]){res[i] = nums2[j];st.pop();}}st.clear();}return res;}
}
相关文章:
代码随想录算法训练营第五十八天丨 动态规划part18
739. 每日温度 思路 首先想到的当然是暴力解法,两层for循环,把至少需要等待的天数就搜出来了。时间复杂度是O(n^2) 那么接下来在来看看使用单调栈的解法。 什么时候用单调栈呢? 通常是一维数组,要寻找任一个元素的右边或者左边…...
Pytest自动化测试框架介绍
1、什么是单元测试框架 单元测试是指在软件开发当中,针对软件的最小单位(函数,方法)进行正确性的检查测试。 2、单元测试框架主要做什么 测试发现:从多个文件里面去找到我们需要的测试用例。 测试执行:按…...
基于SpringBoot+Redis的前后端分离外卖项目-苍穹外卖(五)
公共字段自动填充 1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3 步骤三 1.4 功能测试 1.1 问题分析 在前面我们已经完成了后台系统的员工管理功能和菜品分类功能的开发,在新增员工或者新增菜品分类时需要设置创建时间、创建人、修改时间、修…...
Oracle 监控的指标有哪些和oracle巡检的内容
日常监控指标: 性能指标: 查询响应时间CPU利用率内存利用率磁盘 I/O 活动网络吞吐量 空间管理: 表空间使用率数据文件增长情况Undo 表空间使用率临时表空间使用率 会话和连接: 活跃会话数等待事件监控连接数和连接池效率 数据库对…...
Uniapp有奖猜歌游戏系统源码 带流量主
有奖猜歌游戏是一款基于uni-app、uniCloud、uniAD 开发的小游戏,通过猜歌曲、观看广告赚取现金奖励。 本游戏基本特征如下: 1、玩家可以通过猜歌、做任务等方式直接获取现金奖励 2、玩家可以通过猜歌、拆红包、做任务等方式获取金币奖励,当金币累积到一定数量可以兑换现金 3…...
【算法与数据结构】前言
算法与数据结构是OI中不可或缺的一部分。 今天,让我们走进算法与数据结构独特世界。 性能 算法与数据结构都是完成任务的方法。 方法就要有性能。 有效率就有描述性能的语言。 这就是复杂度。 复杂度的描述 由于复杂度描述的是大致性能,所以采用的是…...
(六)什么是Vite——热更新时vite、webpack做了什么
vite分享ppt,感兴趣的可以下载: Vite分享、原理介绍ppt 什么是vite系列目录: (一)什么是Vite——vite介绍与使用-CSDN博客 (二)什么是Vite——Vite 和 Webpack 区别࿰…...
贝加莱MQTT功能
贝加莱实现MQTT Client端的功能库和例程 导入库和例程,AS Logical View中分别通过Add Object—Library,Add—Program插入MQTT库和例程。 将例程Sample放置于CPU循环周期中 定义证书存放路径,在AS Physical View 中,右击PLC—Con…...
基于JavaWeb+SSM+购物系统微信小程序的设计和实现
基于JavaWebSSM购物系统微信小程序的设计和实现 源码获取入口前言主要技术系统设计功能截图Lun文目录订阅经典源码专栏Java项目精品实战案例《500套》 源码获取 源码获取入口 前言 第一章 绪 论 1.1选题背景 互联网是人类的基本需求,特别是在现代社会,…...
为什么需要Code Review?
1. Code Review 是什么? 代码审查(Code Review)是软件开发过程中对代码进行系统性检查和评审的一项活动。它是指团队成员之间相互检查彼此编写的代码,以确保代码质量、可读性和符合编码标准等。 2. Code Review 的必要性 ● 提…...
【计算机网络笔记】ICMP(互联网控制报文协议)
系列文章目录 什么是计算机网络? 什么是网络协议? 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能(1)——速率、带宽、延迟 计算机网络性能(2)…...
Git教程1:生成和提交SSH公钥到远程仓库
要生成 Git 的公钥并将其提交到远程仓库,你可以按照以下步骤进行操作: 打开命令行终端,并确保已经安装了 Git。在终端中输入以下命令来生成 SSH 密钥对:ssh-keygen -t rsa -b 4096 -C "your_emailexample.com"这将生成…...
贝茄莱BR AS实时数据采集功能
实时数据采集功能在PLC系统调试过程中,有助于调试人员对变量变化进行监测,通过波形对比,反应不同变量间的相互作用。该测试目的在于验证贝加莱系统组态软件的实时数据采集功能。 贝加莱系统组态软件提供Trace功能,连接PLC&#x…...
Git的基本操作以及原理介绍
文章目录 基本操作创建git仓库配置name和email .git目录的结构git add & git commit.git目录结构的变化 git追踪管理的数据git的版本回退回退的原理回退的三种情况 版本库中文件的删除git分支管理分支的删除合并分支时的冲突分支的合并模式分支策略git stash不要在master分…...
2023安全与软工顶会/刊中区块链智能合约相关论文
2023安全与软工顶会/刊中区块链智能合约相关论文 前言软工顶会ISSTAFSEASEICSE 软工顶刊TOSEMTSE 安全顶会S&PUSENIX SecurityCCSNDSS 前言 主要整理了2023年四大安全顶会、四大软工顶会和两个软工顶刊中,有关区块链智能合约的相关论文。 搜索方式是࿱…...
word文档转换为ppt文件,怎么做?
大家是否会遇到需要将word文档转换为ppt文件的情况?除了反反复复粘贴复制以外,还有其他方法可以转换文件格式,今天给大家分享word转换ppt方法。 首先我们先将word文件打开大纲模式 然后我们将文中的大标题设置为1级标题,副标题设…...
机器视觉选型-什么时候用远心镜头
物体厚 当被检测物体厚度较大,需要检测不止一个平面时,典型应用如食品盒,饮料瓶等。 物体位置变化 当被测物体的摆放位置不确定,可能跟镜头成一定角度时。 物体上下跳动 当被测物体在被检测过程中上下跳动,如生产线上下…...
quartz笔记
Quartz-CSDN博客 上面是Quartz的一些基本知识,如果对quartz的基本API不是很了解的话,建议先看下上面的 和Linux Crontab对比 1.执行粒度: Linux Crontab是进程级 quart是线程级 2.跨平台性: Crontab只能在Linxu运行 quart是java实现,可以跨平台 3.调度集上 Crontab的…...
ER 图是什么
文章目录 前言什么是 ER图ER 图实例简化的 ER 图总结 前言 产品经理在梳理产业业务逻辑的过程中,非常重要的一项工作就是梳理各个业务对象之间的关系。如果涉及对象很对的时候,没有工具支持的话很难处理清楚。今天我们就来介绍一个梳理业务对象关系的工…...
PLC电力载波通讯,一种新的IoT通讯技术
前言: PLC-IoT 是 PLC 技术应用在物联场景的创新实践,有效解决电力线路信号干扰、衰减问题,支持 IP 化通信能力,使能终端设备智能化,构建智慧边缘联接。PLC让传统IoT有了更多的连接可能: 电力线通信技术适用的场景包括电力配用电网络、城市智慧路灯、交通路口信号灯、园…...
Elasticsearch:通过摄取管道加上嵌套向量对大型文档进行分块轻松地实现段落搜索
作者:VECTOR SEARCH 向量搜索是一种基于含义而不是精确或不精确的 token 匹配技术来搜索数据的强大方法。 然而,强大的向量搜索的文本嵌入模型只能按几个句子的顺序处理短文本段落,而不是可以处理任意大量文本的基于 BM25 的技术。 现在&…...
OpenCV图像纹理
LBP描述 LBP(Local Binary Pattern,局部二值模式)是一种用来描述图像局部纹理特征的算子;它具有旋转不变性和灰度不变性等显著的优点。它是首先由T. Ojala, M.Pietikinen, 和D. Harwood 在1994年提出,用于纹理特征提取…...
自媒体写手提问常用的ChatGPT通用提示词模板
如何撰写一篇具有吸引力和可读性的自媒体文章? 如何确定自媒体文章的主题和受众群体? 如何为自媒体文章取一个引人入胜的标题? 如何让自媒体文章的开头更加吸引人? 如何为自媒体文章构建一个清晰、逻辑严谨的框架?…...
分类预测 | Matlab实现PSO-LSTM-Attention粒子群算法优化长短期记忆神经网络融合注意力机制多特征分类预测
分类预测 | Matlab实现PSO-LSTM-Attention粒子群算法优化长短期记忆神经网络融合注意力机制多特征分类预测 目录 分类预测 | Matlab实现PSO-LSTM-Attention粒子群算法优化长短期记忆神经网络融合注意力机制多特征分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1…...
3GPP TS38.201 NR; Physical layer; General description (Release 18)
TS38.201是介绍性的标准,简单介绍了RAN的信道组成和PHY层承担的功能,下图是PHY层相关标准的关系。 文章目录 结构信道类型调制方式PHY层支持的过程物理层测量其他标准TS 38.202: Physical layer services provided by the physical layerTS 38.211: Ph…...
【GitLab】-HTTP 500 curl 22 The requested URL returned error: 500~SSH解决
写在前面 本文主要介绍通过SSH的方式拉取GitLab代码。 目录 写在前面一、场景描述二、具体步骤1.环境说明2.生成秘钥3.GitLab添加秘钥4.验证SSH方式4.更改原有HTTP方式为SSH 三、参考资料写在后面系列文章 一、场景描述 之前笔者是通过 HTTP Personal access token 的方式拉取…...
【如何学习Python自动化测试】—— 自动化测试环境搭建
1、 自动化测试环境搭建 1.1 为什么选择 Python 什么是python,引用python官方的说法就是“一种解释型的、面向对象、带有励志语义的高级程序设计语言”,对于很多测试人员来说,这段话包含了很多术语,而测试人员大多是希望利用编程…...
在通用jar包中引入其他spring boot starter,并在通用jar包中直接配置这些starter的yml相关属性
场景 我在通用jar包中引入 spring-boot-starter-actuator 这样希望引用通用jar的所有服务都可以直接使用 actuator 中的功能, 问题在于,正常情况下,actuator的配置都写在每个项目的yml文件中,这就意味着,虽然每个项目…...
Seaborn 回归(Regression)及矩阵(Matrix)绘图
Seaborn中的回归包括回归拟合曲线图以及回归误差图。Matrix图主要是热度图。 1. 回归及矩阵绘图API概述 seaborn中“回归”绘图函数共3个: lmplot(回归统计绘图):figure级regplot函数,绘图同regplot完全相同。(lm指lin…...
nginx学习(1)
一、下载安装NGINX: 先安装gcc-c编译器 yum install gcc-c yum install -y openssl openssl-devel(1)下载pcre-8.3.7.tar.gz 直接访问:http://downloads.sourceforge.net/project/pcre/pcre/8.37/pcre-8.37.tar.gz,就…...
CLEARTEXT communication to XX not permitted by network security policy 报错
在进行网络请求时,日志中打印 CLEARTEXT communication to XX not permitted by network security policy 原因: Android P系统网络访问安全策略升级,限制了非加密的流量请求 Android P系统限制了明文流量的网络请求,之下的版本…...
91.移动零(力扣)
问题描述 代码解决以及思想 class Solution { public:void moveZeroes(vector<int>& nums) {int left 0; // 左指针,用于指向当前非零元素应该放置的位置int right 0; // 右指针,用于遍历数组int len nums.size(); // 数组长度while …...
PatchMatchNet笔记
PatchMatchNet笔记 1 概述2 PatchmatchNet网络结构图2.1 多尺度特征提取2.2 基于学习的补丁匹配 3 性能评价 PatchmatchNet: Learned Multi-View Patchmatch Stereo:基于学习的多视角补丁匹配立体算法 1 概述 特点 高速,低内存,可以处理…...
实时人眼追踪、内置3D引擎,联想ThinkVision裸眼3D显示器创新四大应用场景
11月17日,在以“因思而变 智领未来”为主题的Think Centre和ThinkVision 20周年纪念活动上,联想正式发布了业内首款2D/3D 可切换裸眼3D显示器——联想ThinkVision 27 3D。该产品首次将裸眼2D、3D可切换技术应用在显示器领域,并拓展了3D技术多…...
SELinux零知识学习十四、SELinux策略语言之客体类别和许可(8)
接前一篇文章:SELinux零知识学习十三、SELinux策略语言之客体类别和许可(7) 一、SELinux策略语言之客体类别和许可 4. 客体类别许可实例 (2)文件客体类别许可 文件客体类别有三类许可:直接映像到标准Lin…...
Unity——URP相机详解
2021版本URP项目下的相机,一般新建一个相机有如下组件 1:Render Type(渲染类型) 有Base和Overlay两种选项,默认是Base选项 Base:主相机使用该种渲染方式,负责渲染场景中的主要图形元素 Overlay(叠加):使用了Oveylay的…...
CRUD-SQL
文章目录 前置insertSelective和upsertSelective使用姿势手写sql,有两种方式 一、增当导入的数据不存在时则进行添加,有则更新 1.1 唯一键,先查,后插1.2 批量插1.2.1 批次一200、批次二200、批次三200,有一条数据写入失…...
【C语言 | 数组】C语言数组详解(经典,超详细)
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 🤣本文内容🤣&a…...
第三十三节——组合式API生命周期
一、基本使用 组合式api生命周期几乎和选项式一致。注意组合式api是从挂载阶段开始 <template><div></div> </template> <script setup> import {onBeforeMount, onMounted,onBeforeUpdate, onUpdated, onBeforeUnmount, onUnmounted, } from …...
【Linux】Alibaba Cloud Linux 3 安装 PHP8.1
一、系统安装 请参考 【Linux】Alibaba Cloud Linux 3 中第二硬盘、MySQL8.、MySQL7.、Redis、Nginx、Java 系统安装 二、安装源 rpm -ivh --nodeps https://rpms.remirepo.net/enterprise/remi-release-8.rpm sed -i s/PLATFORM_ID"platform:al8"/PLATFORM_ID&q…...
【容器化】Kubernetes(k8s)
文章目录 概述Docker 的管理痛点什么是 K8s云架构 & 云原生 架构核心组件K8s 的服务注册与发现组件调用流程部署单机版部署主从版本Operator来源拓展阅读 概述 Docker 虽好用,但面对强大的集群,成千上万的容器,突然感觉不香了。 这时候就…...
stm32 HSUSB
/ stm32f407xx.h #define USB_OTG_HS_PERIPH_BASE 0x40040000UL #define USB_OTG_HS ((USB_OTG_GlobalTypeDef *) USB_OTG_HS_PERIPH_BASE) // // 定义全局变量 USBD_HandleTypeDef hUsbDeviceHS;并默认全零初始化/* USB Device handle structure */ typedef struct _USB…...
C# String.Trim 方法
String.Trim()方法定义: 命名空间:System 程序集:System.Runtime.dll 返回结果:返回一个新字符串,它相当于从当前字符串中删除了一组指定字符的所有前导匹配项和尾随匹配项。 Trim方法有三个重载的方法,…...
<Linux>(极简关键、省时省力)《Linux操作系统原理分析之Linux 进程管理 4》(8)
《Linux操作系统原理分析之Linux 进程管理 4》(8) 4 Linux 进程管理4.4 Linux 进程的创建和撤销4.4.1 Linux 进程的族亲关系4.4.2 Linux 进程的创建4.4.3 Linux 进程创建的过程4.4.4 Linux 进程的执行4.4.5 Linux 进程的终止和撤销 4 Linux 进程管理 4.…...
RT-Thread STM32F407 PWM
为了展示PWM效果,这里用ADC来采集PWM输出通道的电平变化 第一步,进入RT-Thread Settings配置PWM驱动 第二步,进入board.h,打开PWM宏 第三步,进入STM32CubeMX,配置时钟及PWM 第四步,回到R…...
idea中把spring boot项目打成jar包
打jar包 打开项目,右击项目选中Open Module Settings进入project Structure 选中Artifacts,点击中间的加号(Project Settings->Artifacts->JAR->From modules with dependencies ) 弹出Create JAR from Modules&#…...
levelDB之基础数据结构-Slice
Slice是levelDB中用于操作字符串的数据结构,以字节为单位。 定义与实现 namespace leveldb {class LEVELDB_EXPORT Slice {public:// Create an empty slice.Slice() : data_(""), size_(0) {}// Create a slice that refers to d[0,n-1].Slice(const c…...
上位机模块之通用重写相机类
在常用的视觉上位机中,我们通常会使用单个上位机匹配多个相机或者多品牌相机,所以在此记录一个可重写的通用相机类,用于后续长期维护开发。 先上代码。 using HalconDotNet; using System.Collections.Generic;namespace WeldingInspection.M…...
机器人导航+OPENCV透视变换示例代码
透视变换又称四点变换,所以不能用于5边形这样的图形变换,不是真正的透视变换,但是这个方法可以把机器人看到的图像转换为俯视图,这样就可以建立地图,要不然怎么建立地图呢。 void CrelaxMyFriendDlg::OnBnClickedOk()…...
KofamScan-KEGG官方推荐的使用系同源和隐马尔可夫模型进行KO注释
文章目录 简介安装使用输入蛋白序列输出detail-tsv格式输出detail格式输出mapper格式 输出结果detail和detail-tsv格式mapper格式常用命令tmp目录 与emapper结果比较其他参数参考 简介 KofamScan 是一款基于 KEGG 直系同源和隐马尔可夫模型(HMM)的基因功…...