Задача: 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. Если стек для данной частоты становится пустым, удалить его.

😎 Решение:

class FreqStack {
    private $freq;
    private $group;
    private $maxfreq;

    function __construct() {
        $this->freq = [];
        $this->group = [];
        $this->maxfreq = 0;
    }

    function push($val) {
        $f = ($this->freq[$val] ?? 0) + 1;
        $this->freq[$val] = $f;
        if ($f > $this->maxfreq) {
            $this->maxfreq = $f;
            $this->group[$f] = [];
        }
        $this->group[$f][] = $val;
    }

    function pop() {
        $val = array_pop($this->group[$this->maxfreq]);
        $this->freq[$val]--;
        if (empty($this->group[$this->maxfreq])) {
            $this->maxfreq--;
        }
        return $val;
    }
}

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