看到题目的第一反应是，这不就是最小堆吗？但是仔细看题，题目要求的四个操作都是在常数时间完成的，最小堆无法达到这样的性能。而且，题目要求的是能够入栈、出栈、看栈顶和看最小值，并没有要求弹出最小值。事实上，如果要每次都弹出最小值，那就只能是最小堆了。

仔细分析，考虑一种基本解法。建立两个栈，一个栈作为常规栈，实现常规的入栈出栈。另一个栈作为最小值栈，存储记录当某次入栈出栈导致最小值变化时，新的最小值。

双栈解法

代码如下。

class MinStack {

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

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty() || minStack.peek() >= x) {
            minStack.push(x);
        }
        stack.push(x);
    }

    public void pop() {
        int temp = stack.pop();
        if (temp == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

获取栈顶只需要调用stack的peek()即可。

获取最小值只需要调用minStack的peek()即可。

每次入栈时，都先检查是否需要操作minStack。如果当前stack为空，那么minStack也为空。或者当前的minStack栈顶大于等于新元素，也需要将新元素x压入minStack。

每次出栈时，都会判断当前出栈值是否等于minStack栈顶，如果等于，说明minStack栈顶对应的最小值已经被弹出，所以也要弹出minStack栈顶。

一个关键点：为什么入栈时判断的条件是minStack.peek() >= x而不是minStack.peek() > x？

因为在出栈时，只要从stack弹出的栈顶等于minStack的栈顶，minStack就需要弹出。所以如果有多个相同的元素存在于stack中，且都等于当前minStack栈顶值，那么minStack就需要弹出多次，同时栈顶依然保存正确的最小值。所以，在入栈时如果minStack.peek() >= x就需要同时入minStack，以保证minStack在多次弹出时依然保存正确的最小值。

单栈解法

考虑只用一个stack解题。

每次入栈时，如果发现了新的最小值，都会先把旧的最小值入栈。出栈时，如果弹出的值等于最小值，那么就多弹一次。需要注意的同样是入栈时的相等判断。

代码如下。

class MinStack {

    int min;
    Stack<Integer> stack;
    /** 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() {
        int temp = stack.pop();
        if (temp == min) {
            min = stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}