(leetcode算法题)155. 最小栈 901. 股票价格跨度

server/2025/1/15 3:44:00/

这两道题都是单调栈专题中的引子题目,

如果我们仔细分析题目,如果只是想得到当前历史数据中最小值和可以发现这两道题,

都不用使用一个额外的容器装以往所有的历史数据才能得到结果

对于155来说,

        只需要维护最小栈就可以快速获得当前的最小元素,而不用通过遍历所有历史数据才能获得最小元素

        首先,如果插入了一个大于最小栈栈顶的元素val,之后无论怎么操作,这个val都不可能成为最小元素,为了解释这一点,我们可以进行分析:

        case1: val比栈中所有历史插入数据都小,

        case2: val和栈中所有历史插入数据中的最小值一样大

        case3: val至少比历史插入数据中的一个数据大

那么如果插入了一个大于最小栈栈顶的元素val,就只能是case3

那么之后如果插入数据都比val大,之前在栈中还是会有小于val的数据,那么之后查询最小值一定不是val

如果不断pop数据,val自然也会被首先pop掉,之后插入的任何值的大小和val本身无关

class MinStack {stack<pair<int, int>> _strecord;
public:MinStack() {_strecord.emplace(make_pair(0, INT_MAX));}void push(int val) {if(val < _strecord.top().second){_strecord.emplace(make_pair(val, val));}else{_strecord.emplace(make_pair(val, _strecord.top().second));}}void pop() {_strecord.pop();}int top() {return _strecord.top().first;}int getMin() {return _strecord.top().second;}
};

对于901来说,这个题要求必须是小于或等于今天价格的最大连续日数

所以从当天往回数,一旦遇到一个比当天价格更高的一天,就立刻停止往前数,那么是否还有必要保存以往的历史价格呢?答案是没必要,只需要知道离当前最近的连续价格下降的那些日子的价格即可,这可以用一个单调栈来保存这些价格

class StockSpanner {
stack<pair<int, int>> decpri_span;
public:StockSpanner() {}int next(int price) {int ret = 1;while(!decpri_span.empty() && decpri_span.top().first <= price){ret += decpri_span.top().second;decpri_span.pop();}decpri_span.emplace(make_pair(price, ret));return ret;}
};


http://www.ppmy.cn/server/158451.html

相关文章

数据结构与算法之二叉树: LeetCode 701. 二叉搜索树中的插入操作 (Ts版)

二叉搜索树中的插入操作 https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/ 描述 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和要插入树中的值 value &#xff0c;将值插入二叉搜索树返回插入后二叉搜索树的根节点。 输入数据 保…

第六章:网页设计

文章目录&#xff1a; 一&#xff1a;网页设计 1.基本概念 1.1 网页 1.2 网站 1.3 工具 2.HTML语言 2.1 基础 2.2 标记 2.2.1 结构 2.2.2 文本 2.2.3 功能 2.2.4 表单 2.3 属性 二&#xff1a;IIS 1.定义 2.主要功能 3.特点与优势 4.应用场景 4.1 安装IIS …

SQL进阶实战技巧:统计相同时刻多地登陆的用户?

目录 0 问题描述 1 数据准备 2 代码实现 3 问题拓展 3.1 查询每个用户登录日期的最大空档期

Git 常用命令及操作流程和注意事项

Git 常用命令及操作流程和注意事项 常用命令 初始化仓库 git init&#xff1a;在当前目录创建一个新的 Git 仓库[3]。 克隆仓库 git clone [url]&#xff1a;从远程仓库克隆到本地[1][3]。 添加文件到暂存区 git add [file]&#xff1a;将指定文件添加到暂存区[4]。git add …

CancerGPT :基于大语言模型的罕见癌症药物对协同作用少样本预测研究

今天我们一起来剖析一篇发表于《npj Digital Medicine》的论文——《CancerGPT for few shot drug pair synergy prediction using large pretrained language models》。该研究聚焦于一个极具挑战性的前沿领域&#xff1a;如何利用大语言模型&#xff08;LLMs&#xff09;在数…

SpringBoot 基础学习

对于SpringBoot的了解&#xff0c;在初学者的角度看来&#xff0c;它是一种工具&#xff0c;用于简化一个Spring项目的初始搭建和开发过程。 1 入门案例 1.1 项目的创建 有四种方法创建&#xff0c;可以通过idea快捷创建&#xff0c;Spring的官网创建&#xff0c;阿里云创建&am…

[3D] 3D雷达天眼监控系统:打造智能城市的安全防线

随着科技的飞速发展&#xff0c;各种智能监控技术不断涌现&#xff0c;为社会的安全保障提供了强大的支持。3D雷达天眼监控系统&#xff0c;作为一种创新的安防监控技术&#xff0c;凭借其强大的环境感知能力和精准的目标探测功能&#xff0c;逐渐成为智能城市、边境防控、交通…

【HUAWEI】HCIP-AI-MindSpore Developer V1.0 | 第四章 图像处理原理与应用(3 AND 4 )

目录 第四章 图像处理原理与应用 3 基于MindSpore的图像处理实践-图像分类 ■ 图像的特性 ▲ 局部感知 ▲ 图像不变性 ■ 卷积神经网络各结构的功能 ▲ CNN核心思想 ■ 图像分类算法的评估指标 ▲ 图像分类的评估指标 ▲ 图像分类评估举例 ■ 基于 MindSpore 的迁移…