# 0895. 最大頻率棧 ## 題目地址（895. 最大頻率棧） <https://leetcode-cn.com/problems/maximum-frequency-stack/> ## 題目描述 ``` <pre class="calibre18">``` 實現 FreqStack，模擬類似棧的數據結構的操作的一個類。 FreqStack 有兩個函數： push(int x)，將整數 x 推入棧中。 pop()，它移除并返回棧中出現最頻繁的元素。 如果最頻繁的元素不只一個，則移除并返回最接近棧頂的元素。 示例： 輸入： ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] 輸出：[null,null,null,null,null,null,null,5,7,5,4] 解釋： 執行六次 .push 操作后，棧自底向上為 [5,7,5,7,4,5]。然后： pop() -> 返回 5，因為 5 是出現頻率最高的。 棧變成 [5,7,5,7,4]。 pop() -> 返回 7，因為 5 和 7 都是頻率最高的，但 7 最接近棧頂。 棧變成 [5,7,5,4]。 pop() -> 返回 5 。 棧變成 [5,7,4]。 pop() -> 返回 4 。 棧變成 [5,7]。 提示： 對 FreqStack.push(int x) 的調用中 0 <= x <= 10^9。 如果棧的元素數目為零，則保證不會調用 FreqStack.pop()。 單個測試樣例中，對 FreqStack.push 的總調用次數不會超過 10000。 單個測試樣例中，對 FreqStack.pop 的總調用次數不會超過 10000。 所有測試樣例中，對 FreqStack.push 和 FreqStack.pop 的總調用次數不會超過 150000。 ``` ``` ## 前置知識 - 棧 - 哈希表 ## 公司 - 暫無 ## 思路 我們以題目給的例子來講解。 - 使用fraq 來存儲對應的數字出現次數。key 是數字，value頻率  - 由于題目限制“如果最頻繁的元素不只一個，則移除并返回最接近棧頂的元素。”，我們考慮使用棧來維護一個頻率表 fraq\_stack。key是頻率，value是數字組成的棧。  - 同時用max\_fraq 記錄當前的最大頻率值。 - 第一次pop的時候，我們最大的頻率是3。由fraq\_stack 知道我們需要pop掉5。  - 之后pop依次是這樣的（紅色數字表示順序）  ## 關鍵點解析 - 棧的基本性質 - hashtable的基本性質 - push和pop的時候同時更新fraq，max\_fraq 和 fraq\_stack。 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">FreqStack</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span> self.fraq = collections.defaultdict(<span class="hljs-keyword">lambda</span>: <span class="hljs-params">0</span>) self.fraq_stack = collections.defaultdict(list) self.max_fraq = <span class="hljs-params">0</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">push</span><span class="hljs-params">(self, x: int)</span> -> <span class="hljs-keyword">None</span>:</span> self.fraq[x] += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> self.fraq[x] > self.max_fraq: self.max_fraq = self.fraq[x] self.fraq_stack[self.fraq[x]].append(x) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pop</span><span class="hljs-params">(self)</span> -> int:</span> ans = self.fraq_stack[self.max_fraq].pop() self.fraq[ans] -= <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> self.fraq_stack[self.max_fraq]: self.max_fraq -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> ans <span class="hljs-title"># Your FreqStack object will be instantiated and called as such:</span> <span class="hljs-title"># obj = FreqStack()</span> <span class="hljs-title"># obj.push(x)</span> <span class="hljs-title"># param_2 = obj.pop()</span> ``` ``` **復雜度分析** - 時間復雜度：push 和 pop 平均時間復雜度是 O(1)O(1)O(1) - 空間復雜度：O(N)O(N)O(N)，其中N為數字的總數。 大家也可以關注我的公眾號《腦洞前端》獲取更多更新鮮的LeetCode題解