895.maximum-frequency-stack.md

题目地址（895. 最大频率栈）

https://leetcode-cn.com/problems/maximum-frequency-stack/

题目描述

实现 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_stack 来维护，将相同频率的数字放到一个栈中。这样频率相同的我们直接出栈就可以取到最接近栈顶的元素啦。存储结构为：

{ 3: [1,2,3], 2: [1,2,3,4], 1: [1,2,3,4,5] } 

上面的结构表示 ：

• 1,2,3 出现了 3 次
• 4 出现了 2 次
• 5 出现了 1 次

细心的同学可能发现了，频率为 2 的列表中同样存储了频率更高（这里是频率为 3）的数字。

这是故意的。比如我们将 3 弹出，那么 3 其实就变成了频率为 2 的数字了。这个时候，我们如何将 3 插入到频率为 2 的栈的正确位置呢？其实你只要按照我上面的数据结构进行设计就没有这个问题啦。

我们以题目给的例子来讲解。

• 使用 fraq 来存储对应的数字出现次数。key 是数字，value 频率

• 由于题目限制“如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。”，我们考虑使用栈来维护一个频率表 fraq_stack。key 是频率，value 是数字组成的栈。

• 同时用 max_fraq 记录当前的最大频率值。

• 第一次 pop 的时候，我们最大的频率是 3。由 fraq_stack 知道我们需要 pop 掉 5。

• 之后 pop 依次是这样的（红色数字表示顺序）

关键点解析

• 栈的基本性质
• hashtable 的基本性质
• fraq_stack 的设计。fraq_stack 中当前频率的栈要保存所有大于等于其频率的数字
• push 和 pop 的时候同时更新 fraq，max_fraq 和 fraq_stack。

代码

classFreqStack: def__init__(self): self.fraq=collections.defaultdict(lambda: 0) self.fraq_stack=collections.defaultdict(list) self.max_fraq=0defpush(self, x: int) ->None: self.fraq[x] +=1ifself.fraq[x] >self.max_fraq: self.max_fraq=self.fraq[x] self.fraq_stack[self.fraq[x]].append(x) defpop(self) ->int: ans=self.fraq_stack[self.max_fraq].pop() self.fraq[ans] -=1ifnotself.fraq_stack[self.max_fraq]: self.max_fraq-=1returnans# Your FreqStack object will be instantiated and called as such:# obj = FreqStack()# obj.push(x)# param_2 = obj.pop()

复杂度分析

这里的复杂度为均摊复杂度。

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。