引言：

实现一个栈，带有出栈、入栈、取最小值三个方法，并要求这三个方法的时间复杂度都为O(1)

最小栈问题

实现一个栈，带有出栈、入栈、取最小值三个方法，并要求这三个方法的时间复杂度都为O(1)

出栈入栈都可以用O(1)实现，最重要的是实现取最小值，最小值我们必须存起来，存在另一个栈中。

如下图，先入栈4、9、7、3、8、5

再出栈三次

import java.util.Stack;

/**
 * @author 董文浩
 * @Date 2020/7/9 21:23
 * 最小栈问题：
 * 实现一个栈，带有出栈、入栈、取最小值三个方法，并要求这三个方法的时间复杂度都为O(1)
 */
public class MinimumStack {
    /**
     * 主栈mainStack，完成正常的栈的使用
     */
    private Stack<Integer> mainStack = new Stack();
    /**
     * 副栈minStack，存储最小的数
     */
    private Stack<Integer> minStack = new Stack();

    /**
     * 入栈
     *
     * @return
     */
    public void push(int e) {
        //如果最小栈为空，或者存入的数值小，那么就将它存入
        if (minStack.isEmpty() || e <= minStack.peek()) {
            minStack.push(e);
        }
        mainStack.push(e);
    }
    /**
     * 出栈
     *
     * @return
     */
    public int pop() {
        //如果出栈的是最小栈内的，就让它也出栈
        if (mainStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        return mainStack.pop();
    }

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

    public static void main(String[] args) {
        MinimumStack stack = new MinimumStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin()); //输出 3
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());// 输出 4
    }
}