【leetcode】全 O(1) 的数据结构

请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 “” 。
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 “” 。

示例：

输入
["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]
[[],["hello"],["hello"],[],[],["leet"],[],[]]
输出
[null,null,null,"hello","hello",null,"hello","leet"]
预期结果
[null,null,null,"hello","hello",null,"hello","leet"]

用双向链表+Map 存储节点信息，将节点按照出现的次数从小到大排序，这样头结点处是计数最小的字符串，尾结点是计数最大的字符串，用map存储字符串key对应的节点位置，这样可以实现O（1）时间复杂度找到对应节点位置。

class AllOne {
    /**
     * 用双向链表+Map 存储节点信息
     */
    class ListNode{
        int val;
        String str;
        ListNode pre;
        ListNode next;
        public ListNode(int val, String str){
            this.val = val;
            this.str = str;
        }

        public void inc(){
            val += 1;
        }

        public void dec(){
            val -= 1;
        }
    }

    Map<String,ListNode> map;
    ListNode head, tail;

    public AllOne() {
        map = new HashMap<>();
        head = new ListNode(0, "");
        tail = new ListNode(Integer.MAX_VALUE, "");
        head.next = tail;
        tail.pre = head;
    }

    public void inc(String key) {
         if(map.containsKey(key)){
             ListNode node = map.get(key);
             //将节点拎出来
             node.next.pre = node.pre;
             node.pre.next = node.next;
             //节点值+1
             node.inc();
             //寻找节点位置
             ListNode tmpNode = node.next;
             while(tmpNode.val<node.val){
                 tmpNode = tmpNode.next;
             }
             //将节点加入链表中
             node.pre = tmpNode.pre;
             tmpNode.pre.next = node;
             tmpNode.pre = node;
             node.next = tmpNode;
         }else{
             //原不存在的节点直接new新的节点插入到头节点下一跳
             ListNode newNode = new ListNode(1, key);
             newNode.next = head.next;
             newNode.pre = head;
             head.next = newNode;
             newNode.next.pre = newNode;
             map.put(key,newNode);
         }
    }

    public void dec(String key) {
        if(map.containsKey(key)){
            ListNode node = map.get(key);
            //将节点拎出来
            node.next.pre = node.pre;
            node.pre.next = node.next;
            //节点值-1
             node.dec();
             if(node.val==0){
                 //如果节点值为0可直接从Map移除，因为前面已经将节点从链表中去掉，所以不需额外处理
                 map.remove(key);
             }else{
                 //从当前节点的前一个节点开始遍历找到插入节点位置
                 ListNode tmpNode = node.pre;
                 while(tmpNode.val>node.val){
                     tmpNode = tmpNode.pre;
                 }
                 //将节点插入链表中
                 node.pre = tmpNode;
                 node.next = tmpNode.next;
                 tmpNode.next.pre = node;
                 tmpNode.next = node;
             }
        }
    }

    public String getMaxKey() {
        if(tail.pre == head) return "";
        return tail.pre.str;
    }  

    public String getMinKey() {
        if(head.next == tail) return "";
        return head.next.str;
    }
             
}