> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/895.-maximum-frequency-stack-h.md).

# 895. Maximum Frequency Stack (H)

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the `FreqStack` class:

* `FreqStack()` constructs an empty frequency stack.
* `void push(int val)` pushes an integer `val` onto the top of the stack.
* `int pop()` removes and returns the most frequent element in the stack.
  * If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

 

**Example 1:**

```
Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

Explanation
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
```

 

**Constraints:**

* `0 <= val <= 109`
* At most `2 * 104` calls will be made to `push` and `pop`.
* It is guaranteed that there will be at least one element in the stack before calling `pop`.

### Solution:

**这种设计数据结构的问题，主要是要搞清楚问题的难点在哪里，然后结合各种基本数据结构的特性，高效实现题目要求的 API**。

那么，我们仔细思考一下 `push` 和 `pop` 方法，难点如下：

1、每次 `pop` 时，必须要知道频率最高的元素是什么。

2、如果频率最高的元素有多个，还得知道哪个是最近 `push` 进来的元素是哪个。

为了实现上述难点，我们要做到以下几点：

1、肯定要有一个变量 `maxFreq` 记录当前栈中最高的频率是多少。

2、我们得知道一个频率 `freq` 对应的元素有哪些，且这些元素要有时间顺序。

3、随着 `pop` 的调用，每个 `val` 对应的频率会变化，所以还得维持一个映射记录每个 `val` 对应的 `freq`。

综上，我们可以先实现 `FreqStack` 所需的数据结构：

```java
class FreqStack {
    // 记录 FreqStack 中元素的最大频率
    int maxFreq = 0;
    // 记录 FreqStack 中每个 val 对应的出现频率，后文就称为 VF 表
    HashMap<Integer, Integer> valToFreq = new HashMap<>();
    // 记录频率 freq 对应的 val 列表，后文就称为 FV 表
    HashMap<Integer, Stack<Integer>> freqToVals = new HashMap<>();
}
```

其实这有点类似前文 [手把手实现 LFU 算法](https://labuladong.github.io/algo/2/20/46/)，注意 `freqToVals` 中 `val` 列表用一个栈实现，如果一个 `freq` 对应的元素有多个，根据栈的特点，可以首先取出最近添加的元素。

要记住在 `push` 和 `pop` 方法中同时修改 `maxFreq`、`VF` 表、`FV` 表，否则容易出现 bug。

现在，我们可以来实现 `push` 方法了：

```java
public void push(int val) {
    // 修改 VF 表：val 对应的 freq 加一
    int freq = valToFreq.getOrDefault(val, 0) + 1;
    valToFreq.put(val, freq);
    // 修改 FV 表：在 freq 对应的列表加上 val
    freqToVals.putIfAbsent(freq, new Stack<>());
    freqToVals.get(freq).push(val);
    // 更新 maxFreq
    maxFreq = Math.max(maxFreq, freq);
}
```

`pop` 方法的实现也非常简单：

```java
public int pop() {
    // 修改 FV 表：pop 出一个 maxFreq 对应的元素 v
    Stack<Integer> vals = freqToVals.get(maxFreq);
    int v = vals.pop();
    // 修改 VF 表：v 对应的 freq 减一
    int freq = valToFreq.get(v) - 1;
    valToFreq.put(v, freq);
    // 更新 maxFreq
    if (vals.isEmpty()) {
        // 如果 maxFreq 对应的元素空了
        maxFreq--;
    }
    return v;
}
```

这样，两个 API 都实现了，算法执行过程如下：

[![](https://labuladong.github.io/algo/images/%e9%ab%98%e9%a2%91%e6%a0%88/1.gif)](https://labuladong.github.io/algo/images/%e9%ab%98%e9%a2%91%e6%a0%88/1.gif)

嗯，这道题就解决了，