【剑指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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年03月23日 08时20分54秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java二叉树求权值_百度笔试题目:二叉树路径权值和【转】
2019-04-21
欧亚马 java折叠车_如何选择欧亚马折叠车?
2019-04-21
python函数代码块以什么开头_Python初体验-开篇 代码全析
2019-04-21
java闹钟程序设计_JAVA课程设计_闹钟的设计与实现项目-报告_附源代码.doc
2019-04-21
php读取大文件某行内容,PHP读取和修改大文件的某行内容_PHP教程
2019-04-21
打印php错误日志,php怎样打印错误日志
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
php把整数拆分成数组,数组拆分处理(整数时的处理),该怎么处理
2019-04-21