LeetCode 895 Maximum Frequency Stack
概述
https://leetcode.com/problems/maximum-frequency-stack/
感觉和 LFU 那道题很像呀。
基于 Map 和双向链表的错误实现
出错的原因：没能保证当 freq 相同时，返回最靠近顶部的元素。
class FreqStack {
public:
int maxFreq = 0;
unordered_map<int, list<int>::iterator> key2iter;
unordered_map<int, list<int>> freq2keyList;
unordered_map<int, int> key2freq;
FreqStack() {
}
void push(int key) {
if (key2freq.count(key) == 0) {
int freq = 1;
maxFreq = max(maxFreq, freq);
freq2keyList[freq].push_front(key);
key2iter[key] = freq2keyList[freq].begin();
key2freq[key] = freq;
return;
}
int oldFreq = key2freq[key]++;
int newFreq = key2freq[key];
freq2keyList[oldFreq].erase(key2iter[key]);
if (freq2keyList[oldFreq].empty()) freq2keyList.erase(oldFreq);
freq2keyList[newFreq].push_front(key);
key2iter[key] = freq2keyList[newFreq].begin();
if (maxFreq == oldFreq) {
maxFreq ++;
}
}
int pop() {
int key = freq2keyList[maxFreq].front();
freq2keyList[maxFreq].pop_front();
key2freq[key]--;
if (maxFreq > 1) {
freq2keyList[maxFreq-1].push_front(key);
key2iter[key] = freq2keyList[maxFreq-1].begin();
} else {
key2freq.erase(key);
key2iter.erase(key);
}
if(freq2keyList[maxFreq].empty()) {
freq2keyList.erase(maxFreq);
if (maxFreq > 0) {
maxFreq--;
}
}
cout << "after pop key " << key << ", maxFreq is " << maxFreq << endl;
return key;
}
};
我们不该把多个相同值作为一个整体处理的，这样就丢失了这些值的位置信息了。
不玩了，Hard 题，不值得。
呜呜呜，offer 要紧，offer 要紧。
基于 Map 和堆栈的实现
https://labuladong.gitee.io/algo/2/20/48/
核心实现：每个频率单独维护一个栈，同时用一个变量当前的最大频率。
class FreqStack {
public:
int maxFreq = 0;
unordered_map<int, int> key2freq;
unordered_map<int, stack<int>> freq2stack;
FreqStack() {}
void push(int key) {
int freq = ++key2freq[key];
freq2stack[freq].push(key);
maxFreq = max(maxFreq, freq);
}
int pop() {
int key = freq2stack[maxFreq].top();
key2freq[key]--;
freq2stack[maxFreq].pop();
if (freq2stack[maxFreq].empty()) {
maxFreq--;
maxFreq = max(maxFreq, 0);
}
return key;
}
};