# \[895]\[困难]\[栈]\[哈希] 最大频率栈

## 题目描述

[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。

## 解题思路

使用哈希表存储每个数字的出现频率, 以频率次数为`key`, `value`为当前栈中该出现频率的数字集合, 以列表的形式存储. 除此之外, 还需要使用一个变量记录当前数字出现的最大频率, 在`push`和`pop`的时候更新哈希表, 以及这个变量.

```python
class FreqStack:

    def __init__(self):
        self.freq = collections.defaultdict(int)
        self.counts = collections.defaultdict(list)
        self.max_freq = 0

    def push(self, x: int) -> None:
        new_freq = self.freq[x] + 1
        self.freq[x] = new_freq
        self.counts[new_freq].append(x)
        self.max_freq = max(self.max_freq, new_freq)

    def pop(self) -> int:
        nums = self.counts[self.max_freq]
        x = nums.pop()
        self.freq[x] -= 1
        if len(nums) == 0:
            self.max_freq -= 1
        return x


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/zhan/895-zui-da-pin-shuai-zhan.md?ask=<question>
```

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.