题目：最大频率栈。

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。FreqStack 有两个函数：
push(int x)，将整数 x 推入栈中。pop()，它移除并返回栈中出现最频繁的元素。如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

示例：

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

出题人：阿里巴巴出题专家：屹平／阿里云视频云边缘计算高级技术专家

参考答案：

令 freq 作为 x 的出现次数的映射 Map。

此外 maxfreq，即栈中任意元素的当前最大频率，因为我们必须弹出频率最高的元素。

当前主要的问题就变成了：在具有相同的（最大）频率的元素中，怎么判断那个元素是最新的？我们可以使用栈来查询这一信息：靠近栈顶的元素总是相对更新一些。

为此，我们令 group 作为从频率到具有该频率的元素的映射。到目前，我们已经实现了 FreqStack 的所有必要的组件。

算法：

实际上，作为实现层面上的一点细节，如果 x 的频率为 f，那么我们将获取在所有 group[i] (i <= f) 中的 x,而不仅仅是栈顶的那个。这是因为每个 group[i] 都会存储与第 i 个 x 副本相关的信息。

最后，我们仅仅需要如上所述维持 freq，group，以及 maxfreq。

参考代码：

class FreqStack {

    Map<Integer, Integer> freq;

    Map<Integer, Stack<Integer>> group;

    int maxfreq;

    public FreqStack() {

        freq = new HashMap();

        group = new HashMap();

        maxfreq = 0;

    }

    public void push(int x) {

        int f = freq.getOrDefault(x, 0) + 1;

        freq.put(x, f);

        if (f > maxfreq) maxfreq = f;

        group.computeIfAbsent(f, z-> new Stack()).push(x);

    }

    public int pop() {

        int x = group.get(maxfreq).pop();

        freq.put(x, freq.get(x) - 1);

        if (group.get(maxfreq).size() == 0)

        maxfreq--;

        return x;

    }

}