题目描述
设计一个支持 push，pop，top 等操作并且可以在 O(1) 时间内检索出最小元素的堆栈。
- push(x)–将元素x插入栈中
- pop()–移除栈顶元素
- top()–得到栈顶元素
- getMin()–得到栈中最小元素
样例
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin(); --> Returns -4.
minStack.pop();
minStack.top(); --> Returns 3.
minStack.getMin(); --> Returns -1.
解法
定义两个stack，一个为存放最小数的序列的辅助栈。
压栈时，先将元素 x 压入 stack1。然后判断 stack2 的情况：
stack2栈为空或者栈顶元素大于x，则将x压入stack2中。stack2栈不为空且栈定元素小于x，则重复压入栈顶元素。
获取最小元素时，从 stack2 中获取栈顶元素即可。
import java.util.Stack;
public class MinStack {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MinStack(){
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x){
stack1.push(x);
if(stack2.isEmpty() || stack2.peek()>x)
stack2.push(x);
else
stack2.push(stack2.peek());
}
public void pop(){
stack1.pop();
stack2.pop();
}
public int top(){
return stack1.peek();
}
public int getMin(){
return stack2.peek();
}
}public static void main(String[] args) {
MinStack obj = new MinStack();
obj.push(-1);
obj.push(3);
obj.push(-4);
obj.push(0);
obj.pop();
int param_3 = obj.top();
int param_4 = obj.getMin();
System.out.println(param_3+ " "+param_4);
}时间复杂度：O(1)、空间复杂度：O(n)
优化
时间复杂度：O(1)、空间复杂度：O(1)
package com.lisen;
import java.util.Stack; public class MinStack {
private Stack<Integer> stack;
private int min; public MinStack(){
stack = new Stack<>();
} public void push(int x){
if(stack.isEmpty()){
min = x;
stack.push(0);
}else{
//计算差值
int compareVal = x - min;
stack.push(compareVal);
min = compareVal < 0 ? x : min;
}
} public void pop(){
int top = stack.peek();
//如果top小于0,显然最小值也一并被删除，此时更新最小值
min = top < 0 ? (min-top) : min;
stack.pop();
} public int getMin(){
return min;
}
}
此方法在数据有限制的情况下适用，否则差值会溢出