Leetcode 895 - Maximum Frequency Stack

題目

Problem#

題目要你實作一個像 stack 的資料結構，但與單純的 stack 不同的是: pop 是看當前元素個數最多的決定的，如果個數相同則越靠近 top 越先被 pop 出來，例如: [5,7,5,7,4,5] 則 pop 順序會是 [5,7,5,4,7,5]

想法#

用一個 heap 維護 (數字個數, 位置, 數字值) 的結構，另外還要維護一個 數字對到個數的結構，和當前的位置。

實作 push() ，先把數值對應到個數然後 + 1，接著推到 heap 中(記得維護位置)；實作 pop() ，只要直接 pop heap 就好，還有個數要 - 1

• 時間複雜度: $\mathcal{O}(n\log{n})$
  • heap 建立
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

Copy

class FreqStack
{
public:
    priority_queue<tuple<int, int, int>> pq; // 第幾個, pos, val
    map<int, int> m; // val -> freq
    int pos = 0;
    
    FreqStack()
    {
    }
    
    void push(int val)
    {
        pq.emplace(++m[val], pos++, val);
    }
    
    int pop()
    {
        auto [freq, pos, val] = pq.top(); pq.pop();
        m[val]--;
        return val;
    }
};

view raw 895.cpp delivered with ❤ by emgithub

賞析#

• 用 stack 的作法
  • 反過來紀錄 個數->數字stack 的 map，並維護目前最大的個數(maxfreq)
  • 實作 push() 就維護 個數->數字stack 和 maxfreq
  • 實作 pop() 根據 maxfreq 從 個數->數字stack 中 pop 一個數字
    • 假如 maxfreq == 0 則把 maxfreq 設成 < 0 的數
  • 這樣 pos 是正確的?
    • 比較後面的數字，會比較晚 stack push 進去 (這裡的 push 指得是我們維護的 stack，而不是題目的 push())
  • $\mathcal{O}(n\log{n})$ or $\mathcal{O}(n)$ (看 map 實作)

心得#

一開始卡在要如何找出個數最多和維護數字對應到個數，原本想說維護數字對到 heap 中的 pair 的 reference (不可行)，沒想到 heap 元素直接塞三個就好