题目链接

155. 最小栈

思路

让栈中的每个结点都额外存储自己入栈时的栈中最小值。这样无论何时，永远能从栈顶元素取出当前栈中的最小值。

代码

class MinStack{

    // key means the number, value means the minimal number
    Stack<Pair<Integer, Integer>> stack;

    public MinStack(){

        this.stack = new Stack<>();
    }

    public void push(int val){

        if(this.stack.empty()){
            this.stack.push(new Pair<>(val, val));
            return;
        }

        this.stack.push(new Pair<>(
			val, 
			Math.min(this.stack.peek().getValue(), val)
			));
    }

    public void pop(){

        this.stack.pop();
    }

    public int top(){

        return this.stack.peek().getKey();
    }

    public int getMin(){

        return this.stack.peek().getValue();
    }
}