问题描述

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

实现 FreqStack 类:

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

提示：

• 0 <= val <= 10^9
• push 和 pop 的操作数不大于 2 * 104。
• 输入保证在调用 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]。

解题思路

本题要实现相应的功能不难，关键是要实现一个类似堆栈的数据结构，每次pop操作都将离栈顶最近的频率最高的元素弹出。那么我们最好记录每个元素的个数，然后再判断是否将其弹出栈。具体做法是，利用C++原有的stack库，记录其中每个元素的出现次数和元素的最大出现次数，每次pop操作时，判断当前元素出现次数是否是最大的，如果不是，则将其保存；如果是，则将其弹出，并判断是否要更新各元素最大出现次数。

但是上述做法存在一个问题，那就是如果栈底元素出现次数最多，那么每次都要pop到接近栈底的元素，然后再将之前弹出的元素压栈，会产生极大的计算开销。一个替代思路是使用多个栈而不是一个栈来实现，不同栈保存出现频率不同的元素，我们每次只需将频率最高的栈的栈顶元素弹出即可。

class FreqStack {
public:
    FreqStack() {
        max_freq = 0;
    }
    
    void push(int val) {
        frequence[val]++;
        if(frequence[val] > max_freq){
            max_freq = frequence[val];
        }
        data[frequence[val]].emplace(val);
    }
    
    int pop() {
        int res = data[max_freq].top();
        data[max_freq].pop();
        if(data[max_freq].empty()){
            max_freq--;
        }
        frequence[res]--;
        return res;
    }
private:
    unordered_map<int, int> frequence;
    unordered_map<int, stack<int>> data;
    int max_freq;
};

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