895. Maximum Frequency Stack

題目網址：https://leetcode.cn/problems/maximum-frequency-stack/

題意：設計一個類似 stack 的資料結構, 將元素 push 到 stack 中, 並從 stack 中 pop 出頻率最高的元素。

請實現 FreqStack class：

FreqStack()：建立一個空的 stack

void push(int val)：將整數 val push 到 stack 中

int pop()：刪除並返回 stack 中頻率最高的元素

若頻率最高的元素不只一個, 則刪除並返回最接近 stack top 的元素

Solution 1：

想法：利用 Bucket, 使用多個 stack, 來模擬 FreqStack。每 push 一個元素就要 push 到當前對應頻率的 stack 中。同一頻率中, 越晚加入的元素就會越接近其對應頻率的 stack 之 top

e.g. push [5, 7, 5, 7, 4, 5], 最後可得到下圖中右下角的表格, 然後依序從 freq 高的開始 pop ➔ pop 的順序由下往上、由右至左為 [5, 7, 5, 4, 7 ,5]

class FreqStack {
public:
    FreqStack() {}

    void push(int val) {
        int freq = ++freqs[val];

        // 若還不存在對應的頻率 stack, 則要新增
        if (stacks.size() < freq) {
            stacks.emplace_back(stack<int>());
        }

        stacks[freq - 1].emplace(val); // push 元素到對應的頻率 stack
    }

    int pop() {
        // 將當前最大頻率且最接近 top 的元素 pop 掉
        const int val = stacks.back().top();
        stacks.back().pop();

        // 若該最大頻率的 stack 中已經沒有任何元素, 則應將其 pop 掉
        // e.g. pop() 一次後, 頻率 = 3 的 stack[2] 中已沒任何元素, 則應將其 pop 掉
        if (stacks.back().empty()) {
            stacks.pop_back();
        }

        --freqs[val];

        return val;
    }

private:
    vector<stack<int>> stacks;
    unordered_map<int, int> freqs;
};

令 n 為 push 的次數

time：
- push()：$O(1)$, push 元素到 stack 中
- pop()：$O(1)$, 從 stack 中 pop 元素
space：$O(n)$ ➔ stacks 中的元素不超過 n 個

Solution 2：

想法：利用 Heap, 概念同 Solution 1, 本題的困難點在於：

每次 pop 時, 必須知道頻率最高的元素是哪個

若頻率最高的元素不只一個, 還得知道最晚 push 進來的元素是哪個

因此, 我們須做到以下幾點：

用 max heap q 來維護當前 stack 中頻率最高的元素

用 timestamp 紀錄每個元素 push 進來的順序(越晚 push 進來的元素, 其 timestamp 越大)

若 q 中有相同頻率的元素, 得用 timestamp 來判斷要優先取哪個。因此 q 中應保存 {freq, timestamp, val}, 這樣當 freq 相同時, top 就會優先取 timestamp 高的元素

class FreqStack {
public:
    FreqStack() : timestamp(0) {}

    void push(int val) {
        q.emplace(++freqs[val], timestamp++, val);
    }

    int pop() {
        const int val = get<2>(q.top());
        q.pop();
        --freqs[val];
        return val;
    }

private:
    int timestamp; // 紀錄元素 push 進來的順序, 越晚表示越大
    unordered_map<int, int> freqs;
    priority_queue<tuple<int, int, int>> q; // max heap, 紀錄 {freq, timestamp, val}
};

令 n 為 push 的次數

time：
- push()：$O(log(n))$, 因為元素 push 到 heap 中, 需調整 heap
- pop()：$O(log(n))$, 因為元素 pop 後, 需調整 heap
space：$O(n)$ ➔ q 中的元素不超過 n 個