解題說明
Maximum Frequency Stack
題目描述：
設計一個類似棧的資料結構 FreqStack，支援兩個操作：
push(val)：將val壓入棧。pop()：移除並返回棧中出現頻率最高的元素。若有多個元素頻率相同，移除最近被壓入的那個。
解題思路： 頻率分組棧：
核心觀察：我們需要同時追蹤「頻率」和「壓入順序」。
維護兩個映射：
freq[val]：記錄每個元素當前的出現次數。freqToStack[f]：一個棧，存放所有「恰好出現 f 次」時被壓入的元素。
另外維護一個 maxFreq 記錄當前最大頻率。
Push：將 val 的頻率 +1，然後將它壓入對應頻率的棧中，更新 maxFreq。
Pop：從 freqToStack[maxFreq] 彈出棧頂元素，將其頻率 -1。若該頻率棧為空，maxFreq--。
這保證了頻率最高且最近壓入的元素被優先彈出。
C++ 解法
複雜度分析
時間複雜度：O(1)（每次 push 和 pop） — 所有操作都是雜湊表查找和棧操作，均為攤銷 O(1)。
空間複雜度：O(n) — 其中 n 是總 push 次數，每次 push 在頻率棧中新增一個元素。
虛擬碼
1. Maintain: freq map (val -> count), freqToStack map (freq -> stack), maxFreq. 2. Push(val): a. Increment freq[val]. b. Update maxFreq = max(maxFreq, freq[val]). c. Push val onto freqToStack[freq[val]]. 3. Pop(): a. Pop val from freqToStack[maxFreq]. b. Decrement freq[val]. c. If freqToStack[maxFreq] is empty, decrement maxFreq. d. Return val.
其他解法
最大堆 + 時間戳：用 (frequency, timestamp, value) 三元組建立最大堆。Push 時插入堆，Pop 時取出堆頂。時間複雜度 O(log n) per operation，空間 O(n)。邏輯簡單但效率不如頻率棧。
有序集合（Ordered Set）：類似堆方案，用 std::set 或 std::map 維護排序。同樣 O(log n) per operation，但常數較大。
延伸思考
- 為什麼
freqToStack[maxFreq]的棧頂一定是「最近被壓入」的最高頻率元素？ - 如果要支援
peekMax()（查看但不移除最高頻率元素），需要修改哪些部分？ - 在多執行緒環境下，如何為此資料結構加鎖以保證執行緒安全？