# leetcode 895 Maximum Frequency Stack

## 思路

stack 的功能在於對於 tie 的部份要用 stack 的方式移除最上面那個，等於說我要能紀錄同一個數字出現的位置。
hash 過去放個 vector 不就好了
所以我今天分 group(hash) -> vector & numberCnt(hash) 記憶對應數量
groupCnt 紀錄某個數量下有幾個數字到達， numberCnt(hash) 紀錄每個數字共有幾個

// Time:  O(1)
// Space: O(n)

class FreqStack {
public:
    FreqStack() {
    }

    void push(int x) {
        ++numberCnt[x];
        groupCnt[numberCnt[x]].push_back(x);
        maxCnt = max(maxCnt, numberCnt[x]);
    } 

    int pop() {
        // 此處不處理 pop empty stack 的 exception
        auto cur = groupCnt[maxCnt].back();
        groupCnt[maxCnt].pop_back();
        numberCnt[cur]--;
        if (groupCnt[maxCnt].empty()) {
            maxCnt--;
        }
        return cur;
    }

private:
    unordered_map<int, vector<int>> groupCnt;
    unordered_map<int, int> numberCnt;
    int maxCnt = 0;
};