716. Max Stack

716. Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax.

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:

1. -1e7 <= x <= 1e7
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

-------------------------
Solution #1
priority queue搞不定，只能treemap。 O(logN)

class MaxStack {
    
    class Node {
        public Node next;
        public Node pre;
        public int val;
        public Node(int val) {
            this.val = val;
            next = null;
            pre = null;
        }
    }
    
    class DoublyLinkedList {
        private Node head;
        private Node tail;
        
        public DoublyLinkedList() {
            head = new Node(0);
            tail = new Node(0);
            head.next = tail;
            tail.pre = head;
        }
        
        public void addToEnd(Node node) {
            node.pre = tail.pre;
            node.pre.next = node;
            node.next = tail;
            tail.pre = node;
        }
        
        public void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;            
        }
        
        public int getLast() {
            return tail.pre.val;
        }
        
        public int removeLast() {
            int tmp = getLast();
            remove(tail.pre);
            
            return tmp;
        }
    }

    private DoublyLinkedList dll;
    private TreeMap<Integer, LinkedList<Node>> map;
    
    /** initialize your data structure here. */
    public MaxStack() {
        dll = new DoublyLinkedList();
        map = new TreeMap<>();
    }
    
    public void push(int x) {
        Node node = new Node(x);
        if (!map.containsKey(x)) {
            map.put(x, new LinkedList<Node>());
        }
        map.get(x).add(node);
        dll.addToEnd(node);
    }
    
    public int pop() {
        int last = dll.removeLast();
        map.get(last).pollLast();
        if (map.get(last).isEmpty()) {
            map.remove(last);
        }
        
        return last;
    }
    
    public int top() {
        return dll.getLast();
    }
    
    public int peekMax() {
        return map.lastKey();
    }
    
    public int popMax() {
        int max = map.lastKey();
        dll.remove(map.get(max).pollLast());
        
        if (map.get(max).isEmpty()) {
            map.remove(max);   
        }
        
        return max;
    }
}

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

Solution #2, 2个stack，ref：https://leetcode.com/problems/max-stack/solution/