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 所需的数据结构：

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 算法，注意 freqToVals 中 val 列表用一个栈实现，如果一个 freq 对应的元素有多个，根据栈的特点，可以首先取出最近添加的元素。

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

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

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 方法的实现也非常简单：

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 都实现了，算法执行过程如下：

嗯，这道题就解决了，