LeetCode 895 Maximum Frequency Stack

标签: 设计数据结构 LeetCode 发布于:2022-02-10 21:21:39 编辑于:2022-02-10 21:39:52 浏览量:415

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/