895. Maximum Frequency Stack

Hard

Description

設計一個類似堆疊的資料結構，支援 push 和 pop 操作：
push(val): 將整數 val 壓入堆疊
pop(): 移除並回傳堆疊中頻率最高的元素。若有多個頻率相同的元素，移除最接近棧頂的那個

Example:

Input: [“FreqStack”, “push”, “push”, “push”, “push”, “push”, “push”, “pop”, “pop”, “pop”, “pop”], [[], [5], [7], [5], [7], [4], [5], [], [], [], []] Output: [null, null, null, null, null, null, null, 5, 7, 5, 4]

Intuition#

核心思路：用 HashMap 記錄每個值的頻率，再用「頻率 -> 堆疊」的映射，pop 時從最高頻率的堆疊取出。

需要追蹤兩個維度：頻率和插入順序
一個值頻率為 3，代表它會出現在頻率 1、2、3 的堆疊中
pop 最高頻率堆疊的棧頂，同時滿足「最高頻率」和「最近 push」兩個條件

Approaches#

⭐1: 頻率分組堆疊#

概念: freqMap 記錄每個值的當前頻率，groupStack 是 Map<Int, Stack>，將每次 push 按頻率分組。維護 maxFreq 追蹤最高頻率
時間複雜度: push 和 pop 均 O(1)
空間複雜度: O(n)

class FreqStack() {
    private val freqMap = HashMap<Int, Int>()      // val -> 當前頻率
    private val groupStack = HashMap<Int, ArrayDeque<Int>>() // freq -> stack of vals
    private var maxFreq = 0

    fun push(`val`: Int) {
        val freq = (freqMap[`val`] ?: 0) + 1
        freqMap[`val`] = freq
        maxFreq = maxOf(maxFreq, freq)

        groupStack.getOrPut(freq) { ArrayDeque() }.addLast(`val`)
    }

    fun pop(): Int {
        val stack = groupStack[maxFreq]!!
        val val_ = stack.removeLast()

        freqMap[val_] = freqMap[val_]!! - 1

        if (stack.isEmpty()) {
            groupStack.remove(maxFreq)
            maxFreq--
        }

        return val_
    }
}

為什麼 maxFreq-- 是正確的？因為 maxFreq 對應的堆疊為空時，下一個最高頻率一定是 maxFreq - 1（每次 push 頻率只增加 1，所以頻率是連續的，不會跳過）。

🔑 Takeaways#

Pattern: 需要按多個維度（頻率 + 順序）排序的問題，頻率分組堆疊是巧妙的解法
關鍵技巧: 一個值頻率為 f 時，它存在於頻率 1 到 f 的所有堆疊中。maxFreq 只需要遞減不需要搜索，因為頻率是連續的。這個設計保證了 push/pop 都是 O(1)