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

力扣75——单调栈

总结leetcode75中的单调栈算法题解题思路。
上一篇:力扣75——区间集合

力扣75——单调栈

  • 1 每日温度
  • 2 股票价格跨度
  • 1 - 2 解题总结

1 每日温度

题目:

给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中
answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都
不会升高,请在该位置用 0 来代替。

题解:
单调栈。
进出栈策略:for循环遍历,对于当前的气温,先跟栈顶比较,如果大于栈顶,则计算栈顶与当前的天数间隔,并出栈,然后继续比较直到不大于,最后将当前气温的日期进栈

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n);stack<int> s;for (int i = 0; i < n; ++i) {while (!s.empty() && temperatures[i] > temperatures[s.top()]) {int previousIndex = s.top();ans[previousIndex] = i - previousIndex;s.pop();}s.push(i);}return ans;}
};

2 股票价格跨度

题目:

设计一个算法收集某些股票的每日报价,并返回该股票当日价格的 跨度 。当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始
往回数,包括今天)。例如,如果未来 7 天股票的价格是 [100,80,60,70,60,75,85],那么股票跨度将是
[1,1,1,2,1,4,6] 。实现 StockSpanner 类:StockSpanner() 初始化类对象。
int next(int price) 给出今天的股价 price ,返回该股票当日价格的跨度。

题解:
单调栈。
进出栈策略:先把一个非常大的数压入栈中,然后for循环遍历。对于当天的股价,先跟栈顶比较,如果大于等雨栈顶,则计算栈顶与当前的天数间隔,并出栈,然后继续比较直到小于最后将当前股价及其日期进栈

class StockSpanner {
public:StockSpanner() {this->stk.emplace(-1, INT_MAX);this->idx = -1;}int next(int price) {idx++;while (price >= stk.top().second) {stk.pop();}int ret = idx - stk.top().first;stk.emplace(idx, price);return ret;}private:stack<pair<int, int>> stk; int idx;
};

1 - 2 解题总结

问题特点1:每个数据都有时间戳、数据间有大小差异。
问题特点2:向后查找,对于某个时间节点的数据,查找其与之后的第几个数据满足某个比较条件;向前查找,对于某个时间节点的数据,查找其与之前的第几个数据满足某个比较条件。
向后查找:由于遍历时,还未知道后面的数据,所以当前数据只是用来计算前面的数据的结果,然后它再进栈。
向前查找:由于遍历时,已经知道当前的数据,所以当前数据是可以得到结果的,至于当前数据是否需要进栈,则需要根据题目具体要求进行判断。

相关文章:

力扣75——单调栈

总结leetcode75中的单调栈算法题解题思路。 上一篇&#xff1a;力扣75——区间集合 力扣75——单调栈 1 每日温度2 股票价格跨度1 - 2 解题总结 1 每日温度 题目&#xff1a; 给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &…...

Webpack和Parcel详解

构建工具和打包器是在开发过程中帮助组织、优化和打包项目的工具。它们可以处理依赖管理、资源优化、代码转换等任务&#xff0c;从而使开发流程更高效。以下是关于构建工具和打包器的一些指导&#xff1a; **Webpack&#xff1a;** Webpack 是一个功能强大的模块打包器&#…...

linux系统服务学习(六)FTP服务学习

文章目录 FTP、NFS、SAMBA系统服务一、FTP服务概述1、FTP服务介绍2、FTP服务的客户端工具3、FTP的两种运行模式&#xff08;了解&#xff09;☆ 主动模式☆ 被动模式 4、搭建FTP服务&#xff08;重要&#xff09;5、FTP的配置文件详解&#xff08;重要&#xff09; 二、FTP任务…...

7.原 型

7.1原型 【例如】 另外- this指向&#xff1a; 构造函数和原型对象中的this都指向实例化的对象 7.2 constructor属性 每个原型对象里面都有个constructor属性( constructor构造函数) 作用&#xff1a;该属性指向该原型对象的构造函数 使用场景: 如果有多个对象的方法&#…...

【图像分类】理论篇(2)经典卷积神经网络 Lenet~Resenet

目录 1、卷积运算 2、经典卷积神经网络 2.1 Lenet 网络构架 代码实现 2.2 Alexnet 网络构架 代码实现 2.3 VGG VGG16网络构架 代码实现 2.4 ResNet ResNet50网络构架 代码实现 1、卷积运算 在二维卷积运算中&#xff0c;卷积窗口从输入张量的左上角开始&#xff…...

C++系列-内存模型

内存模型 内存模型四个区代码区全局区栈区堆区内存开辟和释放在堆区开辟数组 内存模型四个区 不同区域存放的数据生命周期是不同的&#xff0c;更为灵活。 代码区&#xff1a;存放函数体的二进制代码&#xff0c;操作系统管理。全局区&#xff1a;存放全局变量&#xff0c;常…...

[管理与领导-30]:IT基层管理者 - 人的管理 - 向上管理,管理好你的上司,职业发展事半功倍。什么样的上司不值得跟随?

目录 前言&#xff1a; 一、什么是向上管理 二、为什么要向上管理 三、如何进行向上管理 四、向上管理的注意事项 五、向上管理的忌讳 六、向上管理常犯的错 七、如何帮助上司解决他关心的问题 7.1 如何帮助上司解决他关心的问题 7.2 如何帮助上司降低压力 八、什么…...

Java进阶篇--迭代器模式

目录 同步迭代器&#xff08;Synchronous Iterator&#xff09;&#xff1a; Iterator 接口 常用方法&#xff1a; 注意&#xff1a; 扩展小知识: 异步迭代器&#xff08;Asynchronous Iterator&#xff09;&#xff1a; 常用的方法 注意&#xff1a; 总结&#xff1a…...

【CAM】CAM(Class Activation Mapping)——可视化CNN的特征定位

文章目录 一、CAM(Class Activation Mapping)二、CAM技术实现2.1 网络修改2.2 微调2.2 特征提取 三、总结Reference 完整代码见Github &#xff1a;https://github.com/capsule2077/CAM-Visualization &#xff0c;如果有用可以点个Star&#xff0c;谢谢&#xff01; 一、CAM(C…...

Maven教程_编程入门自学教程_菜鸟教程-免费教程分享

教程简介 Maven 是一款基于 Java 平台的项目管理和整合工具&#xff0c;它将项目的开发和管理过程抽象成一个项目对象模型&#xff08;POM&#xff09;。开发人员只需要做一些简单的配置&#xff0c;Maven 就可以自动完成项目的编译、测试、打包、发布以及部署等工作。Maven 是…...

Gof23设计模式之模板方法模式

1.定义 定义一个操作中的算法骨架&#xff0c;而将算法的一些步骤延迟到子类中&#xff0c;使得子类可以不改变该算法结构的情况下重定义该算法的某些特定步骤。 2.结构 模板方法&#xff08;Template Method&#xff09;模式包含以下主要角色&#xff1a; 抽象类&#xff0…...

springBoot 配置文件 spring.resources.add-mappings 参数的作用

在Spring Boot应用中&#xff0c;spring.resources.add-mappings参数用于控制是否将特定路径的资源文件添加到URL路径映射中。 默认情况下&#xff0c;该参数的值为true&#xff0c;即会自动将静态资源&#xff08;例如CSS、JavaScript、图片等&#xff09;的URL路径添加到Spr…...

《Java极简设计模式》第03章:工厂方法模式(FactoryMethod)

作者&#xff1a;冰河 星球&#xff1a;http://m6z.cn/6aeFbs 博客&#xff1a;https://binghe.gitcode.host 文章汇总&#xff1a;https://binghe.gitcode.host/md/all/all.html 源码地址&#xff1a;https://github.com/binghe001/java-simple-design-patterns/tree/master/j…...

C++11并发与多线程笔记(11) std::atomic续谈、std::async深入谈

C11并发与多线程笔记&#xff08;11&#xff09; std::atomic续谈、std::async深入谈 1、std::atomic续谈2、std::async深入理解2.1 std::async参数详述2.2 std::async和std::thread()区别&#xff1a;2.3 async不确定性问题的解决 1、std::atomic续谈 #include <iostream&…...

React快速入门

最近需要学到react&#xff0c;这里进行一个快速的入门&#xff0c;参考react官网 1.创建和嵌套组件 react的组件封装是个思想&#xff0c;我这里快速演示代码&#xff0c;自己本身也不太熟悉。 代码的路径是src底下的App.js function MyButton() {return (<button>I…...

windows权限维持—SSPHOOKDSRMSIDhistorySkeletonKey

windows权限维持—SSP&HOOK&DSRM&SIDhistory&SkeletonKey 1. 权限维持介绍1.1. 其他 2. 基于验证DLL加载—SPP2.1. 操作演示—临时生效2.1.1. 执行命令2.1.2. 切换用户 2.2. 操作演示—永久生效2.2.1. 上传文件2.2.2. 执行命令2.2.3. 重启生效 2.3. 总结 3. 基…...

CSS 两栏布局和三栏布局的实现

文章目录 一、两栏布局的实现1. floatmargin2. flaotBFC3. 定位margin4. flex 布局5. grid布局 二、三栏布局的实现1. float margin2. float BFC3. 定位 margin(或者定位BFC)4. flex布局5. 圣杯布局6. 双飞翼布局 一、两栏布局的实现 两栏布局其实就是左侧定宽&#xff0c;…...

消息中间件相关面试题

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱发博客的嗯哼&#xff0c;爱好Java的小菜鸟 &#x1f525;如果感觉博主的文章还不错的话&#xff0c;请&#x1f44d;三连支持&#x1f44d;一下博主哦 &#x1f4dd;社区论坛&#xff1a;希望大家能加入社区共同进步…...

成集云 | 电子签署集成腾讯云企业网盘 | 解决方案

源系统成集云目标系统 方案介绍 电子签署是通过电子方式完成合同、文件或其他文件的签署过程。相较于传统的纸质签署&#xff0c;电子签署具有更高效、更便捷、更安全的优势。 在电子签署过程中&#xff0c;使用电子签名技术来验证签署者的身份并确保签署文件的完整性。电子…...

提升大数据技能,不再颓废!这6家学习网站是你的利器!

随着国家数字化转型&#xff0c;大数据领域对人才的需求越来越多。大数据主要研究计算机科学和大数据处理技术等相关的知识和技能&#xff0c;从大数据应用的三个主要层面&#xff08;即数据管理、系统开发、海量数据分析与挖掘&#xff09;出发&#xff0c;对实际问题进行分析…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

【大厂机试题+算法可视化】最长的指定瑕疵度的元音子串

题目 开头和结尾都是元音字母&#xff08;aeiouAEIOU&#xff09;的字符串为元音字符串&#xff0c;其中混杂的非元音字母数量为其瑕疵度。比如: “a” 、 “aa”是元音字符串&#xff0c;其瑕疵度都为0 “aiur”不是元音字符串&#xff08;结尾不是元音字符&#xff09; “…...