请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 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"]
解释
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"
提示：
1 <= key.length <= 10key 由小写英文字母组成测试用例保证：在每次调用 dec 时，数据结构中总存在 key最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 10^4 次 分析： 方法：双向链表+哈希表
返回计数最小和最大的字符串，我们可以用一个双向链表来解决，从头到尾计数逐渐增大，这样头就为最小值，尾就为最大值。关于链表的节点，我们可以定义一个整形来表示计数，一个无序集合来存储这个计数的字符串，两个指针分别指向前后。
但是这样只是解决了最大最小计数的问题，关于增加和删除，我们可以用哈希表来实现，键为字符串，值为链表节点。增加时，如果增加后的计数不存在，那么就新建一个节点，并删除旧节点集合中的对应字符串；删除时，如果删除后的计数不存在（0 除外），一样新建一个节点，并删除旧节点集合中的对应字符串。值得注意的是，如果旧节点集合为空，就删除旧节点。
遍历双向链表可能会出现越界情况，我们可以先创建一个头尾节点指向头尾。
时间复杂度：O(1)
空间复杂度：O(n)
class AllOne {
//创建节点
class Node{
//计数
int count;
//集合
Set set = new HashSet<>();
//前指针
Node pre;
//后指针
Node next;
//构造方法
public Node(int _count){
count = _count;
}
//删除方法
public void remove(){
pre.next = next;
next.pre = pre;
}
}
//创建哈希表
Map map;
//创建头尾节点
Node head, tail;
public AllOne() {
map = new HashMap<>();
head = new Node(0);
tail = new Node(Integer.MAX_VALUE);
head.next = tail;
tail.pre = head;
}
public void inc(String key) {
//获取对应节点
Node node = map.getOrDefault(key, head);
//下一个节点不为当前节点计数加1
if(node.next.count != node.count + 1){
//创建新节点
Node newNode = new Node(node.count + 1);
//添加字符串
newNode.set.add(key);
//连接左右节点
Node next = node.next;
node.next = newNode;
newNode.pre = node;
newNode.next = next;
next.pre = newNode;
//更新哈希表
map.put(key, newNode);
}
//下一个节点为当前节点计数加1
else{
node.next.set.add(key);
//更新哈希表
map.put(key, node.next);
}
//删除旧节点对应字符串
//旧节点是头节点
if(node == head){
return;
}
//删除
node.set.remove(key);
//节点集合为空，删除节点
if(node.set.isEmpty()){
node.remove();
return;
}
}
public void dec(String key) {
//获取对应节点
Node node = map.getOrDefault(key, tail);
//上一节点计数为0
if(node.count == 1){
map.remove(key);
}
//上一个节点不为当前节点计数减1 且不为0
else if(node.pre.count != node.count - 1){
//创建新节点
Node newNode = new Node(node.count - 1);
//添加字符串
newNode.set.add(key);
//连接左右节点
Node pre = node.pre;
node.pre = newNode;
newNode.next = node;
newNode.pre = pre;
pre.next = newNode;
//更新哈希表
map.put(key, newNode);
}
//下一个节点为当前节点计数减一
else{
node.pre.set.remove(key);
//更新哈希表
map.put(key, node.pre);
}
//删除旧节点对应字符串
//旧节点是尾节点
if(node == tail){
return;
}
//删除
node.set.remove(key);
//节点集合为空，删除节点
if(node.set.isEmpty()){
node.remove();
}
}
public String getMaxKey() {
for(String s: tail.pre.set){
return s;
}
return "";
}
public String getMinKey() {
for(String s: head.next.set){
return s;
}
return "";
}
}
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-oone-data-structure
