設計一個類似堆疊的資料結構，支援
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
TIP
核心思路：用 HashMap 記錄每個值的頻率，再用「頻率 -> 堆疊」的映射，pop 時從最高頻率的堆疊取出。
- 需要追蹤兩個維度：頻率和插入順序
- 一個值頻率為 3，代表它會出現在頻率 1、2、3 的堆疊中
- pop 最高頻率堆疊的棧頂，同時滿足「最高頻率」和「最近 push」兩個條件
Approaches
1. Brute Force: Scan All on Each Pop — O(n) per pop / O(n)
- Idea: 依 push 順序存進清單；pop 時掃一遍算各值頻率，取頻率最高、同頻取最近 push 的那個
- Time: push
O(1)、popO(n) - Space:
O(n)
class FreqStack() {
private val stack = ArrayList<Int>() // 依 push 順序
fun push(`val`: Int) { stack.add(`val`) }
fun pop(): Int {
val freq = HashMap<Int, Int>()
var bestVal = 0; var bestFreq = 0; var bestIdx = -1
for (i in stack.indices) {
val f = (freq[stack[i]] ?: 0) + 1
freq[stack[i]] = f
if (f >= bestFreq) { bestFreq = f; bestVal = stack[i]; bestIdx = i } // >= 取最近
}
stack.removeAt(bestIdx)
return bestVal
}
}⭐ 2. Frequency-Bucket Stacks — O(1) / O(n)
- Idea:
freqMap記錄每個值的當前頻率，groupStack是Map<Int, Stack>，將每次 push 按頻率分組。維護maxFreq追蹤最高頻率 - Time: push 和 pop 均
O(1) - Space:
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_
}
}WARNING
為什麼 maxFreq-- 是正確的？因為 maxFreq 對應的堆疊為空時，下一個最高頻率一定是 maxFreq - 1（每次 push 頻率只增加 1，所以頻率是連續的，不會跳過）。
🔑 Takeaways
- Pattern: 需要按多個維度（頻率 + 順序）排序的問題，頻率分組堆疊是巧妙的解法
- Key trick: 一個值頻率為 f 時，它存在於頻率 1 到 f 的所有堆疊中。
maxFreq只需要遞減不需要搜索，因為頻率是連續的。這個設計保證了 push/pop 都是 O(1)