D&C

几万年没做LeetCode的题了，更新一下。
https://leetcode.com/problems/all-oone-data-structure/description/
这道题的思路是用一个双向链表(list)来存储一个以value排序的数据结构，使用哈希表(unordered_map)来存储key到链表iterator的映射：

需要注意特殊处理value=1的Node的情况。
代码写得比较毛糙，但是确实是O(1)的复杂度，如果要优化的话map的插入可以用emplace()之类的。
注意：除了value=1的节点，其余节点的keys为空的时候要把该节点删除掉，否则getMaxKey()和getMinKey()就需要O(n)的遍历操作了。

struct KvNode
{
    unordered_set<string> keys;
    int value = 1;
};
class AllOne {
private:
    list<KvNode> value_key;     // arranged by val in ascending order
    using list_it_t = list<KvNode>::iterator;
    unordered_map<string, list_it_t> val_map;
    list_it_t init_node;    //node with value one
public:
    /** Initialize your data structure here. */
    AllOne() {
        value_key.push_back(KvNode());
        init_node = value_key.begin();
    }
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(const string& key) {
        if (val_map.find(key) == val_map.end())
        {
            // `create' new node with value 1
            init_node->keys.insert(key);
            val_map[key] = init_node;
        }
        else
        {
            // find existing node
            auto node_it = val_map[key];
            node_it->keys.erase(key);   //remove from current bulk
            auto next_it = std::next(node_it, 1);
            if (next_it == value_key.end() ||
                 next_it->value != node_it->value + 1)
            {
                // no valid valued bulk, create one
                KvNode node;
                node.keys.insert(key);
                node.value = node_it->value + 1;
                val_map[key] = value_key.insert(next_it, node);
            }
            else
            {
                next_it->keys.insert(key);
                val_map[key] = next_it;
            }
            if (node_it->keys.empty() && node_it->value != 1)
            {
                // remove node_it
                value_key.erase(node_it);
            }
        }
    }
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        auto it_val_map = val_map.find(key);
        if (it_val_map == val_map.end())
        {
            // key does not exist
            return;
        }
        else if (it_val_map->second->value == 1)
        {
            auto node_it = it_val_map->second;
            node_it->keys.erase(key);
            if (node_it->keys.empty() && node_it->value != 1)
            {
                value_key.erase(node_it);
            }
            val_map.erase(it_val_map);
        }
        else
        {
            auto node_it = it_val_map->second;
            auto prev_it = std::prev(node_it, 1);
            node_it->keys.erase(key);
            if (prev_it->value != node_it->value - 1)
            {
                // create one
                KvNode node;
                node.keys.insert(key);
                node.value = node_it->value - 1;
                val_map[key] = value_key.insert(node_it, node);
            }
            else
            {
                prev_it->keys.insert(key);
                val_map[key] = prev_it;
            }
            if (node_it->keys.empty() && node_it->value != 1)
            {
                value_key.erase(node_it);
            }
        }
    }
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        auto it_max = std::prev(value_key.end(), 1);
        if (!it_max->keys.empty())
            return *(it_max->keys.begin());
        else
            return "";
    }
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        auto it_min = value_key.begin();
        if (it_min->value == 1 && it_min->keys.empty())
            ++it_min;
        if (it_min != value_key.end() && !it_min->keys.empty())
            return *(it_min->keys.begin());
        else
            return "";
    }
};
/**
 * 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();
 */