8 包含min函数的栈
2024-08-29 19:55:04
0 引言
题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O().
1 抽象问题具体化
2 具体问题抽象分析
需要解决的两个主要问题如下。
(1)如何在复杂度O(1)的条件下,返回当前栈的最小值。解决思路是定义一个minNum变量保存当前栈的最小值。
(2)另外一个问题是如果当前最小值被弹出了,如何更新minNum的值。解决思路是定义一个新的栈,该栈用于保存次小的值。涉及到两步操作:
1)什么时候入栈:当前入栈的值小于等于最小值时,入栈
2)什么时候出栈:当前出栈值等于最小值时,更新最小值,出栈
3 demo
stack<int> myStack; // 数据栈
stack<int> minorMinNum; // 辅助栈
int minNum = ; // 最小值
void push(int value) {
if(value <= minNum){ // 只有满足当前入栈值小于等于最小值的条件,才将该值压入辅助栈中,同时更新最小值
minorMinNum.push(value);
minNum = value;
}
myStack.push(value);
}
void pop() {
int temp;
if(!myStack.empty()){
temp = myStack.top();
myStack.pop();
}
if(!minorMinNum.empty()){
if(temp == minNum){ // 只有满足当前出栈值等于最小值的条件,更新最小值,同时辅助栈出栈
minorMinNum.pop();
minNum = minorMinNum.top();
}
}
}
int top() {
return myStack.top();
}
int min() {
return minNum;
}
4 代码优化
可以将上述变量minNum给省掉,写法精简如下。
stack<int> myStack;
stack<int> minorMinNum;
void push(int value) {
if(minorMinNum.empty()){
minorMinNum.push(value);
}
else if(value <= minorMinNum.top())
minorMinNum.push(value);
myStack.push(value);
}
void pop() {
if(!myStack.empty() && !minorMinNum.empty()){
if(myStack.top() == minorMinNum.top())
minorMinNum.pop();
myStack.pop();
}
}
int top() {
return myStack.top();
}
int min() {
return minorMinNum.top();
}
最新文章
- 各种图(流程图,思维导图,UML,拓扑图,ER图)简介
- Java xml object 互转
- CodeForces 540C Program D
- keil uvision看厌了么?试试Sublime Text吧!
- java.lang.NullPointerException&;com.cb.action.LoginAction.execute(LoginAction.java:48)
- 【Unity探究】物理碰撞实验
- jqueryUI中datepicker的使用,解决与asp.net中的UpdatePanel联合使用时的失效问题
- ISupportInitialize的用处
- Tornado+MySQL模拟SQL注入
- h5可预览 图片ajax上传 ,后台有点弱不知道数据怎么取,但是可以肯定数据上传成功了
- Beta版本敏捷冲刺每日报告——Day4
- 201621123050 《Java程序设计》第4周学习总结
- hMailServer 邮件服务器搭建
- python开发遇到的坑(2)mongodb安装路径权限问题
- 图解JAVA参数传递
- oracle 数据库链路
- Eclipse环境下如何配置tomcat,并且把项目部署到Tomcat服务器上
- Null和undefined的区别?
- 十大要避免的Ext JS开发方法
- Django模型和ORM