设计一个有getMin功能的栈
【摘要】 设计一个有getMin功能的栈
设计一个有getMin功能的栈
【题目】
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O(1)。
2.设计的栈类型可以使用现成的栈结构。
【思路】
使用两个栈,一个栈a正常的进出,另外一个栈b用来维护最小值,时刻保持b栈的栈顶是当前a栈中的最小值。
方法一【两栈深度不一致】:入栈时,每次入a栈的时候,如果b栈为空,入a栈同时进入b栈,如果入a栈的值比b栈顶大,则不入,反之,进入b栈,更新最小值;出栈时,如果出栈值等于b栈顶,就把b栈顶也出了,更新最小值,反之,b栈不更新。
举例:依次压入3、4、5、1、2、1的过程中,stackData(a)和stackMin(b)的变化如下图所示。
说明:图片来自左神的程序代码面试指南,仅供学习使用。
方法二【两栈深度保持一致】:入栈时,进入a栈时,如果b栈为空,进入b栈,如果b栈不为空且b栈栈顶小于a栈新入栈的值,那么把b栈的栈顶再次入b栈,高度保持一致;出栈时,两个栈同时弹出。
举例:依次压入3、4、5、1、2、1的过程中,stackData(a)和stackMin(b)的变化如下图所示。
【代码】
【Java】
方法一:
package keafmd.accumulate.codeinterviewguide.stackwithgetmin;
import java.util.Stack;
/**
* Keafmd
*
* @ClassName: getMinStack
* @Description: 有最小值的栈
* @author: 牛哄哄的柯南
* @date: 2022-06-20 14:29
*/
public class MyStack1 {
private Stack<Integer> stacka;
private Stack<Integer> stackb;
public MyStack1(){
stacka = new Stack<>();
stackb = new Stack<>();
}
//入栈
public void push(Integer val){
stacka.push(val);
if(stackb.isEmpty()||val<=getMin()){
stackb.push(val);
}
}
//出栈
public Integer pop(){
if(stacka.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
Integer val = stacka.pop();
if(val.equals(getMin())){
stackb.pop();
}
return val;
}
//获取最小值
public Integer getMin(){
if(stackb.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
return stackb.peek();
}
}
方法二:
package keafmd.accumulate.codeinterviewguide.stackwithgetmin;
import java.util.Stack;
/**
* Keafmd
*
* @ClassName: MyStack2
* @Description: 有最小值的栈
* @author: 牛哄哄的柯南
* @date: 2022-06-20 15:07
*/
public class MyStack2 {
private Stack<Integer> stacka;
private Stack<Integer> stackb;
public MyStack2(){
stacka = new Stack<>();
stackb = new Stack<>();
}
//入栈
public void push(Integer val){
stacka.push(val);
if(stacka.isEmpty()||val<getMin()){
stackb.push(val);
}else{
stackb.push(getMin());
}
}
//出栈
public Integer pop(){
if(stacka.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
Integer val = stacka.pop();
stackb.pop();
return val;
}
//获取最小值
public Integer getMin(){
if(stackb.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
return stackb.peek();
}
}
【总结】
方法一和方法二其实都是用 stackb 栈保存着 stacka 每一步的最小值。共同点是所有操作的时间复杂度都为O(1)、空间复杂度都为O(n)。区别是:方法一中stackb压入时稍省空间,但是弹出操作稍费时间;方法二中stackb压入时稍费空间,但是弹出操作稍省时间。
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)