力扣hot100:155. 最小栈(栈,辅助栈存储相关信息)

2024-06-08 13:04

本文主要是介绍力扣hot100:155. 最小栈(栈,辅助栈存储相关信息),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode:155. 最小栈
在这里插入图片描述

1、尝试单调栈

看到这题说,要常数时间内检索最小元素的栈,想到了单调栈,递增单调栈确实能维护最小值,但是这个最小值是存在一定意义的,即如果后面出现了最小值,那么前面的之前的最小值就会无效。

而本题存在弹出操作,这导致当前最小值可能会被丢弃,而需要使用之前的最小值,单调栈可能无法做到找回次小值。

能够弹出值且能一直保持维护数据的最小值的数据结构,是优先队列。因此我们改用优先队列实现。

2、栈+优先队列

如果想要常数级检索到最小元素 且 存在弹出元素,那么需要自定义优先队列,这时在弹出时时间复杂度会高一些。如果不自定义,那就需要延迟出队,这样虽然获取最小值时时间复杂度为高一些,但是弹出时间比较小。

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),堆排序的时间复杂度
  • 空间复杂度: O ( n ) O(n) O(n)
    在这里插入图片描述
class MinStack {
public:MinStack() {}void push(int val) {sta.push(val);nums[val]++;minSta.push(val);}void pop() {int num = sta.top();sta.pop();if(--nums[num] == 0) nums.erase(num);}int top() {return sta.top();}int getMin() {while(nums.count(minSta.top()) == 0) minSta.pop();return minSta.top();}
private:stack<int> sta;priority_queue<int, vector<int>, greater<int>> minSta;unordered_map<int, int> nums;
};

3、辅助栈

方法二,我们使用优先队列实时维护最小值,有必要吗?

要是我们直接使用一个栈为每一个元素维护一个以它为栈顶的栈的最小值,那是不是就OK了?
在这里插入图片描述
即:只要栈顶元素确定了,那么栈中当前的最小值也必然是唯一确定的。我们只需要维护一个元素时最小值的栈就行。

  • 时间复杂度: O ( n ) O(n) O(n),插入只需压栈两次,pop只需弹栈两次,查询是 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( n ) O(n) O(n)
    在这里插入图片描述
class MinStack {
public:MinStack() {min_sta.push(INT_MAX);//这个只是为了方便后面压入少一个条件判断}void push(int val) {sta.push(val);min_sta.push(min(min_sta.top(),val));}void pop() {sta.pop();min_sta.pop();}int top() {return sta.top();}int getMin() {return min_sta.top();}
private:stack<int> sta;stack<int> min_sta;
};

这篇关于力扣hot100:155. 最小栈(栈,辅助栈存储相关信息)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1042265

相关文章

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

SpringBoot3.X 整合 MinIO 存储原生方案

《SpringBoot3.X整合MinIO存储原生方案》本文详细介绍了SpringBoot3.X整合MinIO的原生方案,从环境搭建到核心功能实现,涵盖了文件上传、下载、删除等常用操作,并补充了... 目录SpringBoot3.X整合MinIO存储原生方案:从环境搭建到实战开发一、前言:为什么选择MinI

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

MySQL之InnoDB存储引擎中的索引用法及说明

《MySQL之InnoDB存储引擎中的索引用法及说明》:本文主要介绍MySQL之InnoDB存储引擎中的索引用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录1、背景2、准备3、正篇【1】存储用户记录的数据页【2】存储目录项记录的数据页【3】聚簇索引【4】二

MySQL之InnoDB存储页的独立表空间解读

《MySQL之InnoDB存储页的独立表空间解读》:本文主要介绍MySQL之InnoDB存储页的独立表空间,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、独立表空间【1】表空间大小【2】区【3】组【4】段【5】区的类型【6】XDES Entry区结构【

SQLite3 在嵌入式C环境中存储音频/视频文件的最优方案

《SQLite3在嵌入式C环境中存储音频/视频文件的最优方案》本文探讨了SQLite3在嵌入式C环境中存储音视频文件的优化方案,推荐采用文件路径存储结合元数据管理,兼顾效率与资源限制,小文件可使用B... 目录SQLite3 在嵌入式C环境中存储音频/视频文件的专业方案一、存储策略选择1. 直接存储 vs

CSS3中的字体及相关属性详解

《CSS3中的字体及相关属性详解》:本文主要介绍了CSS3中的字体及相关属性,详细内容请阅读本文,希望能对你有所帮助... 字体网页字体的三个来源:用户机器上安装的字体,放心使用。保存在第三方网站上的字体,例如Typekit和Google,可以link标签链接到你的页面上。保存在你自己Web服务器上的字

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现