algo/ds-class/jing-dian--9ec8b/shu-ju-jie-bbbb1/

[giscus[bot]]

algo/ds-class/jing-dian--9ec8b/shu-ju-jie-bbbb1/

https://labuladong.github.io/algo/ds-class/jing-dian--9ec8b/shu-ju-jie-bbbb1/

[luopan007]

按照博主思路，继续完成c++的题目编写。

class FreqStack {
public:
    FreqStack() {
        valueToFreq.clear();
        freqToList.clear();

        maxFreq = 0;
    }

    // 在栈中加入一个元素 val
    void push(int value) {
        if (valueToFreq.find(value) == valueToFreq.end()) {
            // 该值是第一次加入
            valueToFreq[value] = 1;
        } else {
            // 该值是第N次加入，累加频率
            valueToFreq[value]++;
        }
        freqToList[valueToFreq[value]].emplace_back(value);

        if (valueToFreq[value] > maxFreq) {
            maxFreq = valueToFreq[value];
        }
    }
    
    // 从栈中删除并返回出现频率最高的元素
    // 如果频率最高的元素不止一个，
    // 则返回最近添加的那个元素
    int pop() {
        if (maxFreq <= 0) {
            return -1;
        }

        int target = freqToList[maxFreq].back();
        valueToFreq[target]--;
        freqToList[maxFreq].pop_back();

        if (freqToList[maxFreq].empty()) {
            freqToList.erase(maxFreq);
            maxFreq--;
        }
        return target;
    }

private:
    // 用来记录当前栈里，最大频率
    int maxFreq;

    map<int, int> valueToFreq;

    // 由于一个频率下，可能存在多个元素
    // 在pop的时候，maxFreq 所对应的元素是一个列表，则需要弹出最近入队列的那个元素
    map<int, list<int>> freqToList;
};

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