实现一个数据结构支持以下操作：

Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
挑战：以 O(1) 的时间复杂度实现所有操作。

思路：

这好像是桶排序吧。
1.以出现次数为key创建桶链表，每个桶内装有所有出现次数为某个值的变量，每个key代表一个桶。
2.以输入的string为key创建哈希表，value为对应的桶。
实现代码如下。

class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {
        
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        
        if(!hashmap.count(key))
        {
            if(buckets.empty() || buckets.back().val!=1)
            {
                auto currBucket=buckets.insert(buckets.end(),{1,{key}});
                hashmap[key]=currBucket;
            }
            else
            {
                auto currBucket=--buckets.end();
                currBucket->keys.insert(key);
                hashmap[key]=currBucket;
            }
        }
        else
        {
            auto currBucket=hashmap[key];
            if(currBucket==buckets.begin())
            {
                auto newBucket=buckets.insert(currBucket,{currBucket->val+1,{key}});
                hashmap[key]=newBucket;
            }
            else
            {
                auto lastBucket=--hashmap[key];
                if(lastBucket->val!=currBucket->val+1)
                {
                    auto newBucket=buckets.insert(currBucket,{currBucket->val+1,{key}});
                    hashmap[key]=newBucket;
                }
                else
                {
                    lastBucket->keys.insert(key);
                    hashmap[key]=lastBucket;
                }
                
                
            }
            currBucket->keys.erase(key);
            if(currBucket->keys.empty())
            {
                buckets.erase(currBucket);
            }
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        
        if(hashmap.count(key))
        {
            auto currBucket=hashmap[key];
            if(currBucket->val==1)
            {
                currBucket->keys.erase(key);
                if(currBucket->keys.empty())
                {
                    buckets.erase(currBucket);
                }
                hashmap.erase(key);
                return;
            }
            else
            {
                auto nextBucket=++hashmap[key];
                if(nextBucket==buckets.end() || nextBucket->val!=currBucket->val-1)
                {
                    auto newBucket=buckets.insert(nextBucket,{currBucket->val-1,{key}});
                    hashmap[key]=newBucket;
                    currBucket->keys.erase(key);
                }
                else
                {
                    nextBucket->keys.insert(key);
                    hashmap[key]=nextBucket;
                    currBucket->keys.erase(key);
                }
            }
            if(currBucket->keys.empty())
            {
                buckets.erase(currBucket);
            }
        }
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return buckets.empty()?"":*(buckets.begin()->keys.begin());
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return buckets.empty()?"":*(buckets.rbegin()->keys.begin());
    }
private:
    struct bucket{
        int val;
        unordered_set<string> keys;
    };
    list<bucket> buckets;
    unordered_map<string,list<bucket>::iterator> hashmap;
};

/**
 * 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();
 */