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();
}

最新文章

  1. 各种图(流程图,思维导图,UML,拓扑图,ER图)简介
  2. Java xml object 互转
  3. CodeForces 540C Program D
  4. keil uvision看厌了么?试试Sublime Text吧!
  5. java.lang.NullPointerException&amp;com.cb.action.LoginAction.execute(LoginAction.java:48)
  6. 【Unity探究】物理碰撞实验
  7. jqueryUI中datepicker的使用,解决与asp.net中的UpdatePanel联合使用时的失效问题
  8. ISupportInitialize的用处
  9. Tornado+MySQL模拟SQL注入
  10. h5可预览 图片ajax上传 ,后台有点弱不知道数据怎么取,但是可以肯定数据上传成功了
  11. Beta版本敏捷冲刺每日报告——Day4
  12. 201621123050 《Java程序设计》第4周学习总结
  13. hMailServer 邮件服务器搭建
  14. python开发遇到的坑(2)mongodb安装路径权限问题
  15. 图解JAVA参数传递
  16. oracle 数据库链路
  17. Eclipse环境下如何配置tomcat,并且把项目部署到Tomcat服务器上
  18. Null和undefined的区别?
  19. 十大要避免的Ext JS开发方法
  20. Django模型和ORM

热门文章

  1. HTML5和CSS3工具资源汇总
  2. IDA静态编译之sub
  3. wordpress添加视频弹窗插件Video PopUp
  4. js特效玫瑰花
  5. Delphi 字符串函数 StrUtils(大全)
  6. Dart编程变量
  7. Django -- 高级知识点
  8. PHP headers_list() 函数
  9. delphi windows操作
  10. 2019年12月12日英语学习-Will I Or Won&#39;t I ?