Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

👨‍💻 Алгоритм:

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его.

😎 Решение:

var FreqStack = function() {
    this.freq = new Map();
    this.group = new Map();
    this.maxfreq = 0;
};

FreqStack.prototype.push = function(val) {
    let f = (this.freq.get(val) || 0) + 1;
    this.freq.set(val, f);
    if (f > this.maxfreq) {
        this.maxfreq = f;
        this.group.set(f, []);
    }
    this.group.get(f).push(val);
};

FreqStack.prototype.pop = function() {
    let val = this.group.get(this.maxfreq).pop();
    this.freq.set(val, this.freq.get(val) - 1);
    if (this.group.get(this.maxfreq).length === 0) {
        this.maxfreq--;
    }
    return val;
};

Ставь 👍 и забирай 📚 Базу знаний