432. All O`one Data Structure

Problem:
Implement a data structure supporting the following operations:

1. Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
2. Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
4. GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

Analysis:

Degsin的题，无外乎就那几种数据结构，往上套就行了。 list, linkedlist, doubly linkded list, set, map, queue, stack。LFU用的linked hashmap可以直接放弃，用得太少了。

这道题就是套map和doubly linked list。map解决O(1)查询问题，doubly linked list解决排序问题。靠近head的key count更大。如果是inc(Key), 则比较Key所在node和它prev的大小，超过prev向前以一次。Dec(Key) 操作相反。

head - a - b - c -tail

            3   2   1   

如果上面b加了2次，count变为4，那么就需要把b向前head移一位，变成head - b  - a -  c -tail。

如果是c加了4次，count变为4，因为a,b 的count都比c小了，那么c移到a,b的前面变成head - c - a - b - tail。

GetMaxKey返回的是head.next.val, GetMinKey反之。

感觉自己的代码比leetcode discussion 上面大多数要强。

Solution:

move forward 和move back里面用while的原因是，有可能会出现超过一个比当前节点值小或者大的节点。
向前向后移分2次操作，先romove再insert。 

class AllOne {
    class DoublyLinkedNode {
        int val;
        String key;
        DoublyLinkedNode prev;
        DoublyLinkedNode next;
        public DoublyLinkedNode(int val, String key) {
            this.val = val;
            this.key = key;
        }
    }

    DoublyLinkedNode head;
    DoublyLinkedNode tail;
    Map<String, DoublyLinkedNode> map;
    /** Initialize your data structure here. */
    public AllOne() {
        head = new DoublyLinkedNode(0, "");
        tail = new DoublyLinkedNode(0, "");
        map = new HashMap<>();
        head.next = tail;
        tail.prev = head;
    }
    
    private void remove(DoublyLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void insertAHead(DoublyLinkedNode front, DoublyLinkedNode back) {    
        front.next = back;
        back.prev.next = front;
        front.prev = back.prev;
        back.prev = front;
    }

    
    private void moveForward(DoublyLinkedNode node) {
        while (node.prev != head && node.val > node.prev.val) {
            DoublyLinkedNode prev = node.prev;
            remove(node);
            insertAHead(node, node.prev);
        }
    }

    private void moveBackward(DoublyLinkedNode node) {
        while (node.next != tail && node.val < node.next.val) {
            DoublyLinkedNode next = node.next;
            remove(node.next);
            insertAHead(next, node);
        }
    }



    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (!map.containsKey(key)) {
            DoublyLinkedNode node = new DoublyLinkedNode(1, key); 
            map.put(key, node);
            insertAHead(node, tail);
        } else {
            DoublyLinkedNode node = map.get(key);
            node.val++;
            moveForward(node);
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (map.containsKey(key)) {
            DoublyLinkedNode node = map.get(key);
            node.val--;
            if (node.val == 0) remove(node);
            else moveBackward(node);
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if (map.isEmpty()) {
            return "";
        } else 
        {
            return head.next.key;
        }
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
         if (map.isEmpty()) {
            return "";
        } else 
        {
            return tail.prev.key;
        }
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */