// 只想到了用一个数据结构维护最小的元素,也想到了用栈,但是没有想到如何保证O(1)的复杂度。
维护一个辅助栈,每次都把最小的元素压入辅助栈,保证在辅助栈栈顶的元素一直是最小的。

import java.util.Stack;

public class Solution {

    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    public void push(int node) {
        stack1.push(node);
        if (stack1.empty()) {
            stack2.push(node);
        } else {
            int min = Math.min(node, stack2.peek());
            stack2.push(min);
        }
    }

    public void pop() {
        stack1.pop();
        stack2.pop();
    }

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

    public int min() {
        return stack2.peek();
    }
}