0895. 最大频率栈 · ttttt

# 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">``` class FreqStack: def __init__(self): self.fraq = collections.defaultdict(lambda: 0) self.fraq_stack = collections.defaultdict(list) self.max_fraq = 0 def push(self, x: int) -> None: self.fraq[x] += 1 if self.fraq[x] > self.max_fraq: self.max_fraq = self.fraq[x] self.fraq_stack[self.fraq[x]].append(x) def pop(self) -> int: ans = self.fraq_stack[self.max_fraq].pop() self.fraq[ans] -= 1 if not self.fraq_stack[self.max_fraq]: self.max_fraq -= 1 return ans # Your FreqStack object will be instantiated and called as such: # obj = FreqStack() # obj.push(x) # param_2 = obj.pop() ``` ``` **复杂度分析** - 时间复杂度：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)