Java PriorityQueue + Map + Doubly Linked Node Solution


  • 0
    D

    The idea is to only put distinct values in the priorityqueue so that when we are removing or adding duplicates we don't have to use O(logn) time to reorder. The time complexity is O(logn)/O(1) for push/pop/popMax and O(1) for top and peek.

    Few more thoughts:

    1. It is impossible to do all O(1) since we have to keep order.
    2. To remove an element from a 'list' like structure in O(1) I chose to use doubly linked list.
    3. Hence we have to keep track of where the nodes are in a hashmap. Adding and removing from the end is O(1) in this case (which is essentially a stack).
    class MaxStack {
        class DLNode {
            DLNode prev;
            DLNode next;
            int val;
            public DLNode(int x) {
                val = x;
                prev = null;
                next = null;
            }
        } 
        
        int FAKE = 10000007;
        
        PriorityQueue<Integer> q;
        Map<Integer, List<DLNode>> m;
        DLNode tail;
        
        /** initialize your data structure here. */
        public MaxStack() {
            q = new PriorityQueue();
            m = new HashMap();
            tail = new DLNode(FAKE);
        }
        
        public void push(int x) {
            DLNode node = new DLNode(x);
            if (!m.containsKey(x)) m.put(x, new ArrayList());
            List<DLNode> l = m.get(x);
            if (l.size() == 0) q.add(-x);
            l.add(node);
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        
        public int pop() {
            DLNode node = tail;
            int x = node.val;
            List<DLNode> l = m.get(x);
            l.remove(l.size() - 1);
            if (l.size() == 0) q.remove(-x);  
            tail = node.prev;
            tail.next = null;
            return x;
        }
        
        public int top() {
            return tail.val;
        }
        
        public int peekMax() {
            return -1*q.peek();
        }
        
        public int popMax() {
            int x = -1*q.peek();
            List<DLNode> l = m.get(x);
            DLNode node = l.get(l.size() - 1);
            if (node == tail) return pop();
            l.remove(l.size() - 1);
            DLNode p = node.prev;
            DLNode n = node.next;
            p.next = n;
            n.prev = p;
            if (l.size() == 0) q.poll();
            return x;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.