Java TreeMap and Double LinkedList


  • 1
    S
    class MaxStack {
    
        Node head;
        Node tail;
        TreeMap<Integer, List<Node>> map;
        
        public MaxStack() {
            head = new Node(0);
            tail = new Node(0);
            head.next = tail;
            tail.pre = head;
            map = new TreeMap<>();
        }
        
        public void push(int x) {
            Node newNode = new Node(x);
            newNode.pre = tail.pre;
            newNode.next = tail;
            tail.pre.next = newNode;
            tail.pre = newNode;
            if(!map.containsKey(x))    map.put(x, new ArrayList<Node>());
            map.get(x).add(newNode);
        }
        
        public int pop() {
            int value = tail.pre.val;
            removeNode(tail.pre);
            int listSize = map.get(value).size();
            map.get(value).remove(listSize - 1);
            if(listSize == 1)    map.remove(value);
            return value;
        }
        
        public int top() {
            return tail.pre.val;
        }
        
        public int peekMax() {
            return map.lastKey();
        }
        
        public int popMax() {
            int maxVal = map.lastKey();
            int listSize = map.get(maxVal).size();
            Node node = map.get(maxVal).remove(listSize - 1);
            removeNode(node);
            if(listSize == 1)    map.remove(maxVal);
            return maxVal;
        }
        
        private void removeNode(Node n){
            Node preNode = n.pre;
            Node nextNode = n.next;
            preNode.next = nextNode;
            nextNode.pre = preNode;
        }
        
        class Node{
            Node pre;
            Node next;
            int val;
            public Node(int x){
                this.val = x;
                this.pre = null;
                this.next = null;
            }
        }
    }
    

Log in to reply
 

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