432. All O`one Data Structure

https://leetcode.com/problems/all-oone-data-structure/

在hash map基础上额外支持O(1)时间查询出现频率最大和最小的元素。思路和LFU cache类似，双向链表结点的值代表freq，结点内再存该freq下的所有key。

/*
 * @lc app=leetcode id=432 lang=cpp
 *
 * [432] All O`one Data Structure
 */

// @lc code=start
class AllOne {
public:
    class Node {
    public:
        int val;
        unordered_set<string> keys;
        Node *next = nullptr, *prev = nullptr;
        Node(int v): val(v) {}
    };
    Node *head, *tail;
    unordered_map<string, Node*> m;
    /** Initialize your data structure here. */
    AllOne() {
        head = new Node(0);
        tail = head;
    }

    Node *next(Node *old) {
        if (old->next == nullptr || old->next->val != old->val + 1) {
            auto next = old->next, new_n = new Node(old->val + 1);
            old->next = new_n;
            new_n->next = next;
            new_n->prev = old;
            if (next != nullptr) next->prev = new_n;
        }
        return old->next;
    }

    void rm(Node *node) {
        node->prev->next = node->next;
        if (node->next != nullptr) node->next->prev = node->prev;
    }

    Node *prev(Node *old) {
        if (old->prev->val != old->val - 1) {
            auto prev = old->prev, new_n = new Node(old->val - 1);
            old->prev = new_n;
            prev->next = new_n;
            new_n->next = old;
            new_n->prev = prev;
        }
        return old->prev;
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if (!m.count(key)) {
            auto one = next(head);
            m[key] = one;
            (one->keys).insert(key);
        } else {
            auto *old = m[key], *new_n = next(old);
            old->keys.erase(key); 
            if (old->keys.empty()) {
                rm(old);
            }
            new_n->keys.insert(key);
            m[key] = new_n;
        }
        if (tail->next != nullptr) {
            tail = tail->next;
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if (!m.count(key)) return;
        auto *old = m[key], *new_n = prev(old);
        old->keys.erase(key); 
        if (old->keys.empty()) {
            if (tail == old) tail = new_n;
            rm(old);
        }
        if (new_n == head) {
            m.erase(key);
            return;
        }
        new_n->keys.insert(key);
        m[key] = new_n;
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if (tail == head) return "";
        return *(tail->keys.begin());
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if (tail == head) return "";
        return *(head->next->keys.begin());
    }
};

/**
 * 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();
 */
// @lc code=end