# 0895. 最大频率栈
### 题目地址（895. 最大频率栈）
### 题目描述
```
实现 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。
### 代码
```python
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()
```
**复杂度分析**
这里的复杂度为均摊复杂度。
* 时间复杂度：$O(1)$
* 空间复杂度：$O(1)$
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/895.maximum-frequency-stack.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.