方法一
使用两个栈。
class MinStack {
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> stack_min = new ArrayDeque<>();
public MinStack() {
}
public void push(int x) {
stack.push(x);
if(stack_min.isEmpty() || stack_min.peek() >= x){
stack_min.push(x);
}
}
public void pop() {
int pop = stack.pop();
if(pop == stack_min.peek()){
stack_min.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
return stack_min.peek();
}
}方法二
重复保存最小值： 当最小值要被替代的时候，将上一个最小值再加入一次栈，这样当当前最小值弹出时，还能找到上一个最小值。
class MinStack {
Deque<Integer> stack = new ArrayDeque<>();
int min = Integer.MAX_VALUE;
public MinStack() {
}
public void push(int x) {
if(x <= min){
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
int pop = stack.pop();
if(pop == min) min = stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return min;
}
}方法三
保存当前值和最小值的差值： 当栈顶元素为负数的时候，表示上一个min被替换了，此时需要还原上一个min。
class MinStack {
Deque<Long> stack = new ArrayDeque<>();
long min = Integer.MAX_VALUE;
public MinStack() {
}
public void push(int x) {
if(stack.isEmpty()){
min = x;
stack.push(0L);
}else{
stack.push(x - min);
if(x < min) min = x;
}
}
public void pop() {
long pop = stack.pop();
if(pop < 0){ // 当栈顶元素为负数的时候，表示上一个min被替换了，此时需要还原上一个min
min = min - pop;
}
}
public int top() {
long pop = stack.peek();
if(pop < 0){
return (int) min;
}else{
return (int) (min + pop);
}
}
public int min() {
return (int) min;
}
}