[移动开发]895. 最大频率栈

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

实现 FreqStack 类:

??? FreqStack() 构造一个空的堆栈。
??? void push(int val) 将一个整数 val 压入栈顶。
??? int pop() 删除并返回堆栈中出现频率最高的元素。
??????? 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

示例 1：

输入：
["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]
解释：
FreqStack = new FreqStack();
freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]
freqStack.push (4);//堆栈是 [5,7,5,7,4]
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。

提示：

??? 0 <= val <= 109
??? push 和 pop 的操作数不大于 2 * 104。
??? 输入保证在调用 pop 之前堆栈中至少有一个元素。

方法：栈

思路

显然，我们更关心元素的频率。令 freq 作为 xxx 到 xxx 的出现次数的映射 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;
    }
}

题意

??? 插入一个元素
??? 返回栈中，出现频率最高，最近插入的元素，删掉。注意，只删掉最近插入的，参考样例1。
??? 步骤
??????? 用哈希表记录每个元素出现的频次。
??????? 使用multiset将频次最高，最接近栈顶的元素放在集合开头。
??????? 更新元素频次，删掉集合头部元素。

class FreqStack {
public:
    struct node{
        int key, val, index;
        bool operator <(const node& a)const{
            if(val != a.val){
                return val > a.val;
            }
            return index > a.index;
        }
    };
    multiset<node> S;
    unordered_map<int, int> mp;
    int index;
    FreqStack() {
        index = 0;
    }
    
    void push(int val) {
        mp[val]++;
        S.insert({val, mp[val], index});
        index++;
    }
    
    int pop() {
        int key = S.begin()->key;
        S.erase(S.begin());
        
        mp[key]--;
        return key;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */