题目

第一种解法题解思路

维护两个栈，一个输入栈，一个辅助栈，辅助栈用于存储当前栈中的最小值。
因为pop一定是从栈顶出栈的，所以在辅助栈中后入栈的最小值影响不到先入栈的最小值。
出栈时，输入栈和辅助栈一起出，因为辅助栈栈顶的最小值是相对于输入栈栈顶而言的。

第一种解法图解思路

辅助栈为空，所以之间进入辅助栈。

2进入栈里面，因为2 < 3

4 进入辅助栈，可以看到4比辅助栈栈顶元素大，为了保持辅助栈栈顶是最小值，此时不能把4放进去了。

必须放一个2进去，也就是辅助栈的栈顶元素。

我们来出栈看一下。

可以看到同时出栈，辅助栈栈顶始终是最小值。

Java

class MinStack {
    Stack<Integer> A, B;
    /** initialize your data structure here. */
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    
    public void push(int x) {
        A.push(x);
        if (B.empty() || x < B.peek()) { // 辅助栈B为空 或者x小于B的栈顶元素，那么把x入B栈，这样B顶部始终是最小值
            B.push(x);
        } else {
            B.push(B.peek());  // x比B栈顶元素大，那么B栈顶是最小元素，继续B继续入一个栈顶的最小元素。
        }
    }
    
    public void pop() { 
        A.pop();
        B.pop();
    }
    
    public int top() {
        return A.peek();
    }
    
    public int min() { // B栈顶维护了一个最小值
        return B.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.min();
 */

第二种题解思路

每步都是使用头插法，在头结点前面插入一个节点。同时头节点中保留一个最小值。
出栈就是返回头结点的下一个节点。

Java

class MinStack {
    //链表头，相当于栈顶
    private ListNode head;

    //压栈，需要判断栈是否为空
    public void push(int x) {
        if (empty())
            head = new ListNode(x, x, null);
        else
            head = new ListNode(x, Math.min(x, head.min), head);
    }

    //出栈，相当于把链表头删除
    public void pop() {
        if (empty())
            throw new IllegalStateException("栈为空……");
        head = head.next;
    }

    //栈顶的值也就是链表头的值
    public int top() {
        if (empty())
            throw new IllegalStateException("栈为空……");
        return head.val;
    }

    //链表中头结点保存的是整个链表最小的值，所以返回head.min也就是
    //相当于返回栈中最小的值
    public int min() {
        if (empty())
            throw new IllegalStateException("栈为空……");
        return head.min;
    }

    //判断栈是否为空
    private boolean empty() {
        return head == null;
    }
}

class ListNode {
    public int val;
    public int min;//最小值
    public ListNode next;

    public ListNode(int val, int min, ListNode next) {
        this.val = val;
        this.min = min;
        this.next = next;
    }
}

第三种思路

使用单栈实现最小min函数的栈。

当压栈的值小于栈中最小值时，先把最小值入栈，然后再把需要压栈的值入栈，最后再更新栈中最小值。如果压栈的值大于栈中最小值的时候，直接压栈。

核心思想：单栈用一个全局变量min保存最小值，然后每次入栈是除了更新这个min，还需要保留上一次的最小值，这样在出栈的时候，可以获取到上一次的最小值，来更新min值。

出栈：

接下来是1出栈，1就是当前全局最小值1。1出栈了以后，那么需要找1出栈以后的全局最小值，也就是找1的上一次的全局最小值2。

现在栈的样子：

同理继续出栈，2出栈也就是，2由于就是当前全局最小值2，所以出栈步骤和刚才的1出栈步骤一样。也是出栈2次，同时把第二次出栈的6赋值到全局最小值6上。

现在的栈的样子：

继续6出栈，6是最后一个元素，直接出栈。

Java代码

class MinStack {//push方法可能会加入很多min
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<>();

    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 min() {
        return min;
    }
}