【剑指Offer】包含min函数的栈
发布日期:2022-02-10 08:55:13 浏览次数:24 分类:技术文章

本文共 1313 字,大约阅读时间需要 4 分钟。

题目

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();

minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示:

各函数的调用总次数不超过 20000 次

思路

最一开始想着每次在push的时候直接更新下最小值就行了,没想到pop的情况。。

为了实现时间复杂度是O(1),可以采用存储的时候存的不是实际值,而是实际值与最小值的差值。

但是这种代码我没写出来,换思路

除了一个常规列表实现栈的操作外,再开一个辅助栈用于保存当前的最小信息:

入栈操作:当辅助栈为空或者新元素小于等于辅助栈顶元素时,辅助栈入栈;否则无视

出栈操作:当常规栈中待出栈的元素等于辅助栈顶元素时,辅助栈出栈一个元素,代表当前的最小值出队或者次数减1
栈顶操作:仅需从常规栈顶取元素即可
最小值操作:因为辅助栈中维护的都是当前状态下的最小值,所以从辅助栈顶取元素即可
另外,利用and的短路特性实现对两个栈非空判断,确保操作的稳健性。

代码

class MinStack {public:    int mini;    stack
sta; stack
stb; /** initialize your data structure here. */ MinStack() { } void push(int x) { if(stb.empty() || x <= stb.top()){ stb.push(x); } sta.push(x); } void pop() { if(sta.top() == stb.top()){ stb.pop(); } sta.pop(); } int top() { return sta.top(); } int min() { return stb.top(); }};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->min(); */

 

转载地址:https://blog.csdn.net/hanmin822/article/details/105610750 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【剑指Offer】1~n整数中1出现的次数
下一篇:【剑指Offer】栈的压入、弹出序列

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月23日 08时20分54秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java 执行 awk_3.1 biostar lesson3 linux学习日记;java版本;awk 2019-04-21
java二叉树求权值_百度笔试题目:二叉树路径权值和【转】 2019-04-21
欧亚马 java折叠车_如何选择欧亚马折叠车? 2019-04-21
python函数代码块以什么开头_Python初体验-开篇 代码全析 2019-04-21
java闹钟程序设计_JAVA课程设计_闹钟的设计与实现项目-报告_附源代码.doc 2019-04-21
java中的无效的列类型_java.sql.SQLException: 无效的列类型: 1111 2019-04-21
php rewrite url_PHP_URL Rewrite的设置方法,URL Rewrite需要服务器的支持! - phpStudy 2019-04-21
php读取大文件某行内容,PHP读取和修改大文件的某行内容_PHP教程 2019-04-21
打印php错误日志,php怎样打印错误日志 2019-04-21
Calendar导入java,Java程序使用Calendar.add()方法将分钟添加到当前时间 2019-04-21
mysql中用户线程作用,mysql用户线程的建立与用户线程的状态源码解析 2019-04-21
php页面引用公共文件,WeiPHP插件模板中快速引入公共模板文件 2019-04-21
php tracy,admin.php 2019-04-21
php访问父类的所有属性,php – 在父类中使用$this仅在子类中显示父类属性 2019-04-21
oracle比较强大的函数,SQL和ORACLE函数比较 2019-04-21
oracle12c order by,oracle 数据库中order by 的一些高级用法 2019-04-21
oracle8i substr,Oracle中的INSTR,NVL和SUBSTR函数的用法详解 2019-04-21
导出oracle11g的空表,轻松解决oracle11g 空表不能 exp 导出 的问题。 2019-04-21
php把整数拆分成数组,数组拆分处理(整数时的处理),该怎么处理 2019-04-21
oracle numlist,oracle sql str2numlist numtabletype 2019-04-21