432. 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.

S： hash list

关键是如何以O(1)得到min max，这里用一个类似matrix的结构：

row1: val: 1 {key1, key2};

row2: val: 3 {key3};

row3: val: 4 {key4, key5, key6}

每行是递增的，用list<int, unordered_set<string>>实现此结构，list首尾即为min，max值。

用unordered_map<string, list<valToKeys>::iterator>实现对list元素O(1)的访问

注意同步更新 list 和 hashmap

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 (keyToVal.find(key) == keyToVal.end() && valList.front().val != 1) {  // key not exist,   
            valList.push_front(valToKeys(1, unordered_set<string>{key}));        // last value is not 1, push back
            keyToVal[key] = valList.begin();
        } else if (keyToVal.find(key) == keyToVal.end()) { // key not exist
            valList.front().keys.insert(key);              // last value is one, insert
            keyToVal[key] = valList.begin(); 
        } else {                                          // key exist  
            auto cur = keyToVal[key];
            auto after = next(cur);
            cur->keys.erase(key);
            if (after != valList.end() && after->val == cur->val + 1) {
                after->keys.insert(key);
            } else {
                valList.insert(after, valToKeys(cur->val + 1, unordered_set<string>{key}));
            }
            keyToVal[key] = next(cur);
            if (cur->keys.empty()) {
                valList.erase(cur);
            }
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if (keyToVal.find(key) == keyToVal.end()) {
            return;
        }
        auto cur = keyToVal[key];
        cur->keys.erase(key);
        if (cur->val > 1) { 
            if (cur == valList.begin() || prev(cur)->val != cur->val - 1) {
                valList.insert(cur, valToKeys(cur->val - 1, unordered_set<string>{key}));
            } else {
                prev(cur)->keys.insert(key);
            }
            keyToVal[key] = prev(cur);
        }
        else {
            keyToVal.erase(key);   
        }
        if (cur->keys.empty()) {
            valList.erase(cur);
        }
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return valList.empty()? "" : *valList.back().keys.begin();
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return valList.empty()? "" : *valList.front().keys.begin();
    }

private:
    struct valToKeys{
        int val;
        unordered_set<string> keys;
        valToKeys(int v, unordered_set<string> k) : val(v), keys(k) {};
    };
    list<valToKeys> valList;  //ordered value list
    unordered_map<string, list<valToKeys>::iterator> keyToVal;
};