895. 最大頻率棧

思路

題目要求實現stack的修改版。在pop時要彈出出現次數最多的數字，如果相同就選最近放入的。
因此需要額外紀錄每個元素出現的頻率，並且為每一個頻率都單獨創一個stack出來。
假如插入的資料是 $[a,b,b,a]$ ，會發生以下的事情：

1. 插入資料a

• freq[a] = 1，發現stks沒有針對出現頻率1創建對應的棧，先創建。
• stks[freq[a]].push(a)，將a放到對應的stack當中。

2. 插入資料b

• freq[b] = 1，stks有創建對應的棧。
• stks[freq[b]].push(b)，此時stks[1] = {a, b}

3. 插入資料b

• freq[b] = 2，stks沒有創建對應的棧，先創建。
• stks[freq[b]].push(b)，此時stks[2] = {b}

4. 連續插入兩次a，最後的樣子

• freq[a] = 3, freq[b] = 2
• stks[3] = {a},stks[2] = {b, a}, stks[1] = {a, b}

如果pop，就取stks.back()（紀錄出現最多頻率的棧），並取得棧頂元素（最新資料）。
舉例來說，在第三步之後pop，就會取到stks[2].top() = b

程式碼

棧

class FreqStack {
private:
    unordered_map<int, int> freq; // 元素對應的出現頻率
    vector<stack<int>> stks; // 出現頻率對應的stack
public:
    FreqStack() {}
    void push(int val) {
        if(freq[val] == stks.size()) { // 需要新的 stack
            stks.push_back(stack<int>());
        }
        stks[freq[val]].push(val);
        freq[val]++;
    }
    
    int pop() {
        int val = stks.back().top();
        stks.back().pop();
        if(stks.back().empty()) {
            stks.pop_back();
        }
        freq[val]--;
        return val;
    }
};

複雜度分析

• 時間複雜度：$O(1)$。
• 空間複雜度：$O(q)$，$q$為 $\text{push}$ 的調用次數。