895. Maximum Frequency Stack

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.

• If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

class FreqStack {
    unordered_map<int, list<int>> m;
    map<int, list<int>> sizeMap;
    int cnt = 0;
public:
    FreqStack() {
    }
    void push(int x) {
        m[x].push_back(cnt++);
        sizeMap[(int)m[x].size()].push_back(x);
    }

    int pop() {
        auto res = rend(sizeMap)->second.back();
        sizeMap[(int)m[res].size()].pop_back();
        if(sizeMap[(int)m[res].size()].empty())
            sizeMap.erase((int)m[res].size());
        m[res].pop_back();
        return res;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 */