面试题 03.02. 栈的最小值

解题思路

执行push、pop和min操作的时间复杂度必须为O(1)
1.分析题意，由于有时间复杂度O(1)的限制，所以需要存储的数据有minValueList、list
2.存储每个数据的当前值的同事，需要存储当前值的最小值

解题遇到的问题

1.可以用双栈的思路解题

后续需要总结学习的知识点

无

##解法
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;
    }

    public int getMin() {
        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;
    }
}