leetcode155.最小栈

题目链接

解题思路一：two stack

本题的解题思路很简单，用两个栈即可完成。一个栈作为普通的栈存储数据，另一个栈每次随着main栈同步push,pop，不过每次push操作都向其中压入当前最小的元素。
代码如下：

class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;


    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }
    
    public void push(int x) {
        if(stack.isEmpty()){
            stack.push(x);
            minStack.push(x);
        }else{
            stack.push(x);
            if(x < minStack.peek()){
                minStack.push(x);
            }else{
                minStack.push(minStack.peek());
            }
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {  
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

代码执行结果如下：

解题思路二：only one stack

本题除了可以使用辅助的mainStack和minStack两个栈的方法解决该问题，也可以只使用一个栈来完成，具体思路为：实时维护一个变量min。每次push(x)操作的时候，如果x <= min的时候，先将min进栈，再将x进栈；在pop操作的时候，如果取出来的元素是等于当前的min，那么就再执行一次pop操作，并将min更新。
代码如下：

class MinStack {

    private Stack<Integer> stack;
    private int min;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        if(x <= min){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }
    
    public void pop() {
        if(stack.pop() == min){
            min = stack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

执行结果：