432.全O(1)的数据结构

题目：

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

实现 AllOne 类：

AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。
注意：每个函数都应当满足 O(1) 平均时间复杂度。

输入
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
输出
[null, null, null, "hello", "hello", null, "hello", "leet"]

解释
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "hello"
allOne.inc("leet");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "leet"

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/all-oone-data-structure
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的思路：

对每一个字符串都要对应一名计数君，因此我们将字符串和计数君绑定起来。又为了能够以O(1)的时间复杂度找到这个字符串和它对应的计数君，我就想到把这个字符串作为key，计数君作为val，存放到哈希表中，以方便查找。因此在构造器中，我们要创建一个哈希表来满足我们的查找服务。

同时为了能够返回最大和最小的计数值，我想着在Allone类中定义变量max和min还有maxKey和minKey来存放最大最小值和最长字符串和最短字符串。但是问题来了，当某个字符串的计数君减到0的时候，这个字符串就要从哈希表中删去，而此时最小的计数君是多少呢？如果没有用其他数据结构的话，我们就得遍历一遍所有的字符串，这就违反了题目要求的所有的操作时间复杂度都是O(1)。因此，双向链表应运而生；

我们再创建一个类---结点，结点存放字符串和它的计数君，还有next 和 prev 前后结点。同时为它做一些实用的函数

class MapNode{
    String str = "";
    int val;
    MapNode next;
    MapNode prev;

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public MapNode(String str) {
        this.str = str;
    }

    public MapNode() {
    }
}

结点处理完了，就来处理双向链表。为了一下子就能找到最大最小值，双向链表要升序排列(或者降序也行，我这里写的是升序)。当字符串计数增加的时候，我们要查看它的计数值是否大于后一个结点的计数值，当字符串计数减少的时候，我们也得查看它的计数值是否小于前一个结点的计数值，如果发现不满足升序排列，就要将前后两个结点相互交换。而当减少的时候，还得注意它是不是到0了，到了的话就将它删除。增加时也要查看哈希表中是否存在这个字符串，不存在，则增加。

class DoubleLinkedList{
    MapNode head;
    MapNode tail;

    public DoubleLinkedList() {
        head = new MapNode();
        tail = new MapNode();

        head.next = tail;
        tail.prev = head;
    }
    public void delLeast(MapNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    public void swapNode(MapNode little,MapNode big){
        little.next = big.next;
        big.prev = little.prev;
        little.prev.next = big;
        big.next.prev = little;
        little.prev = big;
        big.next = little;
    }
    public void addHead(MapNode node){
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
        node.setVal(1);
    }
    
}

这时候回看我们的哈希表，哈希表的val已经不能仅仅存放我们的计数君了，因为这样就跟我们的链表对应不上了，因此哈希表应该存放的key为字符串，而val则是对应的结点

在我提交的时候，发现了一个问题，就是前文在交换的时候仅仅交换了一次，如果这个时候有下面这样的案例：1,1,1,1,1,2  ，如果是第一个1增加，就不能只和它后面的结点交换，应该一直交换到2前边。

剩余代码如下：

public class AllOne {
    HashMap<String,MapNode> map;
    DoubleLinkedList list;

    public AllOne() {
        map = new HashMap<>();
        list = new DoubleLinkedList();
    }

    public void inc(String key) {
        if(map.containsKey(key)){
            MapNode node = map.get(key);
            node.val++;
            while(node.next!=list.tail&&node.val>node.next.val){
                list.swapNode(node,node.next);
            }
        }else {
            MapNode mapNode = new MapNode(key);
            list.addHead(mapNode);
            map.put(key,mapNode);
        }
    }

    public void dec(String key) {
        MapNode node = map.get(key);
        node.val--;
        if(node.val==0){
            list.delLeast(node);
            map.remove(key);
            return;
        }
        while(node.prev!=list.head&&node.val<node.prev.val){
            list.swapNode(node.prev,node);
        }
    }

    public String getMaxKey() {
        return list.tail.prev.str;
    }

    public String getMinKey() {
        return list.head.next.str;
    }
}