问题入口
O(1)
#include <iostream>
#include <unordered_map>
#include <stack>
using namespace std;
class FreqStack {
public:
unordered_map<int, int> freq;
unordered_map<int, stack<int>> freq_stack;
int max_freq;
FreqStack() {
max_freq = 0;
}
void push(int val) {
max_freq = max(max_freq, ++freq[val]);
freq_stack[freq[val]].push(val);
}
int pop() {
int ret = freq_stack[max_freq].top();
freq_stack[max_freq].pop();
freq[ret]--;
if(!freq_stack[max_freq].size()) max_freq--;
return ret;
}
};pop的要求是先找到出现次数最高的元素，再返回距离栈顶最近的元素。
使用unordered_map<int, stack<int>>类型可以满足这样存储，以频次分类元素并以栈的结构存储。
unordered_map<int, int> freq用于存储每个元素的频次。freq每次变化都记录在freq_stack中，或者说freq被录入为freq_stack元素的键。
max_freq用于记录最高频次。注意：最高频次的元素被pop之后，下一次最高频次就是max_freq-1。例如，[1, 1, 1]，最高频次是3；删除完栈顶元素后是[1,1]，最高频次是2。
超时
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
class FreqStack {
public:
unordered_map<int, int> map;
vector<int> array;
int max_freq_ele;
int max_freq;
FreqStack() {
max_freq_ele = 0;
max_freq = 0;
}
int add(unordered_map<int, int>& map, int val)
{
if(map.find(val) != map.end()) //If the key is not found, it is equal to map.end().
map[val]++;
else
map[val] = 1;
return map[val];
}
void push(int val) {
array.push_back(val);
int num = add(map, val);
if(num >= max_freq)
{
max_freq = num;
max_freq_ele = val;
}
}
int pop() {
auto it = find(array.rbegin(), array.rend(), max_freq_ele);
if(it != array.rend()){
auto index = array.rend() - it - 1;
array.erase(array.begin() + index);
if (map[max_freq_ele] != 1)
map[max_freq_ele]--;
else
map.erase(max_freq_ele);
}
int ret = max_freq_ele;
max_freq = 0;
for (auto it = array.begin(); it != array.end(); it++)
{
if(max_freq <= map[*it])
{
max_freq = map[*it];
max_freq_ele = *it;
}
}
return ret;
}
};
