895. Max Frequency Stack

Maximum Frequency Stack

这种题的关键 通常都看pop()方法想干嘛

要我们移除且返回栈中频率最高的元素

如果频率最高的元素有多个并列 选最接近栈顶的

最接近栈顶的翻译：最晚被纳入的

因此需要对每个频率维持栈的结构

才好在Tiebreaker下 拿到最晚被纳入的元素

栈中栈

架构描绘

(1). 频率栈：这是 外层 结构 每当本来最高的频率

其所含元素被清光 这个频率就不再是最高

需要挪出栈 让栈顶留给下一个频率体现变化

(2). 元素栈：这是 内层 结构 每个频率有专属元素栈

同样频率下 越晚升上来这频率的元素 越靠近栈顶

正是题目强调的Tiebreaker的体现

因此我们先开个frequencyStack的外栈

栈上每个索引$i$ 代表频率$i$

每个频率$i$上又内栈 储存频率为$i$的元素

方法实现

一、push(int value)：一旦被呼叫

先在哈希表给value的出场频率+1

假设更新后的频率来到了$x$

就在外栈上寻找索引为$x$的内栈

把value放到这个内栈最顶端

因此如果发现$x$等于外栈长度时

说明目前外栈只反映到频率$x - 1$

需要在外栈顶开个新内栈储存频率$x$

二、pop()：每次运作时 首先将外栈上

最顶部的内栈 弹出其栈顶元素

在哈希表把被弹元素的频率-1

这便是频率最高的元素中最接近栈顶的

接著检查外栈顶的内栈是否被清空

空掉的话 自然也请这个内栈弹离开外栈

精确反映目前最大频率的变化

C++

#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;

class MaxFrequencyStack // LeetCode Q.895.
{
private:
    // Each idx contains stack of values with frequency = idx.
    // Pad empty stack to adjust for 0-based indexing.
    vector<stack<int>> frequencyStack = {{}};

    unordered_map<int, int> valuesFrequencies;

public:
    MaxFrequencyStack() {}

    void push(int value) {
        valuesFrequencies[value]++;
        int frequency = valuesFrequencies[value];

        // Need to add another stack for current frequency.
        if (frequency == frequencyStack.size())
            frequencyStack.push_back({});

        frequencyStack[frequency].push(value);
    }

    int pop() {
        int mostFreqValue = frequencyStack.back().top();
        valuesFrequencies[mostFreqValue]--;

        frequencyStack.back().pop();
        if (frequencyStack.back().empty())
            frequencyStack.pop_back();

        return mostFreqValue;
    }
};

Python

class MaxFrequencyStack:  # LeetCode Q.895.
    def __init__(self):
        self.vals_freqs: dict[int, int] = dict()

        # Each idx contains stack of values w/ frequency = idx.
        # Pad empty stack to adjust for 0-based indexing.
        self.freqs_stacks: list[list[int]] = [[]]
    
    def push(self, value: int) -> None:
        if value not in self.vals_freqs.keys():
            self.vals_freqs.update({value: 0})
        self.vals_freqs[value] += 1

        # Need to add another stack for current frequency.
        if self.vals_freqs[value] == len(self.freqs_stacks):
            self.freqs_stacks.append([])

        frequency = self.vals_freqs[value]
        self.freqs_stacks[frequency].append(value)

    def pop(self) -> int:
        most_freq_val = self.freqs_stacks[-1].pop(-1)

        if not self.freqs_stacks[-1]: self.freqs_stacks.pop(-1)

        self.vals_freqs[most_freq_val] -= 1
        return most_freq_val

时间复杂度在push(int value)和pop()都是$O(1)$ 空间则是有$O(n)$

可别像Algo Monster搞heaps弄成$O(logn)$时间复杂度欸