leetcode-895 最大频率栈

题目描述：实现 FreqStack，模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数：

• push(int x)，将整数 x 推入栈中。
• pop()，它移除并返回栈中出现最频繁的元素。
  如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

代码实现

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

public FreqStack() {
}

public void push(int val) {
    //1. 计算每个元素出现的频率
    int frequency = this.valToFreq.getOrDefault(val, 0);
    frequency++;
    this.valToFreq.put(val, frequency);

    //2. 计算最大频率
    maxFreq = maxFreq >= frequency ? maxFreq : frequency;

    //3. 计算频率对应元素栈
    Stack<Integer> valStack = this.freqToVals.getOrDefault(frequency, new Stack<>());
    valStack.add(val);
    this.freqToVals.put(frequency, valStack);
}

public int pop() {
    //1. 取出弹出元素
    int val = this.freqToVals.get(maxFreq).pop();

    //2. 重新计算当前元素频率
    int frequency = this.valToFreq.get(val);
    frequency--;
    this.valToFreq.put(val, frequency);

    //3. 当前频率已经没有元素了，需要重新计算最大频率
    if (this.freqToVals.get(maxFreq).isEmpty()) {
        maxFreq = frequency;
    }
    return val;
}

}
```