716. Max Stack

class Node {
    int val;
    Node next, prev;

    Node(int val) {
        this.val = val;
    }
}

class MaxStack {

    Node head, tail;

    TreeMap<Integer, ArrayList<Node>> maxs;

    public MaxStack() {
        head = new Node(-1);
        tail = new Node(-1);
        head.next = tail;
        tail.prev = head;
        maxs = new TreeMap<>();
    }

    private void insertNode(Node node) {
        Node next = head.next;
        head.next = node;
        node.next = next;
        next.prev = node;
        node.prev = head;
    }

    public void push(int x) {
        Node node = new Node(x);
        if (!maxs.containsKey(x)) maxs.put(x, new ArrayList<>());
        insertNode(node);
        maxs.get(x).add(node);
    }

    private void removeNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
        node.next = null;
        node.prev = null;
        List<Node> list = maxs.get(node.val);
        maxs.get(node.val).remove(list.size() - 1);
        if (maxs.get(node.val).isEmpty()) maxs.remove(node.val);
    }


    public int pop() {
        Node popNode = head.next;
        int pop = popNode.val;
        removeNode(popNode);
        return pop;
    }

    public int top() {
        return head.next.val;
    }

    public int peekMax() {
        return maxs.lastEntry().getKey();
    }

    public int popMax() {
        List<Node> list = maxs.lastEntry().getValue();
        Node popNode = list.get(list.size() - 1);
        removeNode(popNode);
        return popNode.val;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */