😲716 Max Stack

https://leetcode.com/problems/max-stack/

class MaxStack {
    private class Node {
        int val;
        Node pre;
        Node next;
        public Node(int val) {
            this.val = val;
            pre = null;
            next = null;
        }
    }
    private TreeMap<Integer, Deque<Node>> map;
    private Node head;
    private Node tail;
    public MaxStack() {
        map = new TreeMap<>();
        head = new Node(-1);
        tail = new Node(-1);
        head.next = tail;
        tail.pre = head;
    }
    
    public void push(int x) {
        Deque<Node> stack = map.get(x);
        if (stack == null) {
            stack = new ArrayDeque<>();
        }
        Node node = new Node(x);
        insert(node);
        stack.offerFirst(node);
        map.put(x, stack);
    }
    
    public int pop() {
        Node node = head.next;
        int val = node.val;
        Deque<Node> stack = map.get(val);
        stack.pollFirst();
        if (stack.isEmpty()) {
            map.remove(val);
        }
        remove(node);
        return val;
    }
    
    public int top() {
        Node node = head.next;
        return node.val;
    }
    
    public int peekMax() {
        int key = map.lastKey();
        Deque<Node> stack = map.get(key);
        return stack.peekFirst().val;
    }
    
    public int popMax() {
        int key = map.lastKey();
        Deque<Node> stack = map.get(key);
        Node node = stack.pollFirst();
        if (stack.isEmpty()) {
            map.remove(key);
        }
        remove(node);
        return node.val;
    }
    
    private void insert(Node node) {
        Node next = head.next;
        head.next = node;
        node.pre = head;
        node.next = next;
        next.pre = node;
    }
    private void remove(Node node) {
        if (node.next == null || node.pre == null) {
            return;
        }
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
        
        node.next = null;
        node.pre = null;
    }
}

/**
 * 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();
 */

类似LRU，利用双向链表和treeMap，treeMap可以快速找到最大的key(lastKey)，链表可以快速insert和remove，同时还保证顺序