<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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頻率 ![](https://img.kancloud.cn/e3/56/e3560b8ea5b5470ed2daf8cf9ba555ae_468x766.jpg) - 由于題目限制“如果最頻繁的元素不只一個,則移除并返回最接近棧頂的元素。”,我們考慮使用棧來維護一個頻率表 fraq\_stack。key是頻率,value是數字組成的棧。 ![](https://img.kancloud.cn/ea/d9/ead9835172f29a0381c81d1d52c3d2c6_722x656.jpg) - 同時用max\_fraq 記錄當前的最大頻率值。 - 第一次pop的時候,我們最大的頻率是3。由fraq\_stack 知道我們需要pop掉5。 ![](https://img.kancloud.cn/f5/b0/f5b003ae97b6600ff605eb4ab28dd6bc_1338x838.jpg) - 之后pop依次是這樣的(紅色數字表示順序) ![](https://img.kancloud.cn/70/14/70144761f1dcb55aab511521aeb11f67_920x738.jpg) ## 關鍵點解析 - 棧的基本性質 - 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題解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看