All O`one Data Structure

题目
Implement a data structure supporting the following operations:

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.
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.
GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
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.

答案

class AllOne {
    class DoublyListNode{
        int val;
        String key;
        DoublyListNode prev;
        DoublyListNode next;
        DoublyListNode(int x, String k) { val = x; key = k;}
    }
    List<DoublyListNode> list;
    Map<String, DoublyListNode> map;

    /** Initialize your data structure here. */
    public AllOne() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {

        // If key does not exists, create a new node and the mapping
        DoublyListNode node = map.get(key);
        if(node == null) {
            node = new DoublyListNode(1, key);
            map.put(key, node);
        }
        // If key exists, add node value by 1
        else {
            node.val = node.val + 1;
        }

        // Expand list if node.val >= list size
        if(node.val > list.size()) {
            DoublyListNode list_head = new DoublyListNode(node.val, "");
            list_head.prev = list_head;
            list_head.next = list_head;
            list.add(list_head);
        }

        // If new node val > 1, this means we should first remove it from bucket[node.val - 1]
        if(node.val > 1) {
            // Remove from bucket data structure
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        // Add node to the right bucket
        DoublyListNode bucket = list.get(node.val - 1);
        DoublyListNode next = bucket.next;
        bucket.next = node;
        node.prev = bucket;
        node.next = next;
        next.prev = node;
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        DoublyListNode node = map.get(key);
        if(node != null) {
            if(node.val == 1) {
                // Remove from map
                map.remove(key);
            }
            node.val = node.val - 1;

            // Remove from bucket[node.val]
            node.prev.next = node.next;
            node.next.prev = node.prev;

            // Add to new bucket
            if(node.val > 0) {
                DoublyListNode bucket = list.get(node.val - 1);
                DoublyListNode next = bucket.next;
                bucket.next = node;
                node.prev = bucket;
                node.next = next;
                next.prev = node;
            }

        }
    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        for(int i = list.size() - 1; i >= 0; i--) {
            DoublyListNode node = list.get(i);
            if(node.next == node) continue;
            return node.next.key;
        }
        return "";
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        for(int i = 0; i < list.size() ; i++) {
            DoublyListNode node = list.get(i);
            if(node.next == node) continue;
            return node.next.key;
        }
        return "";
    }
}