[895][困难][栈][哈希] 最大频率栈

题目描述

895. 最大频率栈

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数：

• push(int x)，将整数 x 推入栈中。

• pop()，它移除并返回栈中出现最频繁的元素。

  • 如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

示例：

输入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

提示：

• 对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。

• 如果栈的元素数目为零，则保证不会调用 FreqStack.pop()。

• 单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。

• 单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。

• 所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。

解题思路

使用哈希表存储每个数字的出现频率, 以频率次数为key, value为当前栈中该出现频率的数字集合, 以列表的形式存储. 除此之外, 还需要使用一个变量记录当前数字出现的最大频率, 在push和pop的时候更新哈希表, 以及这个变量.

class FreqStack:

    def __init__(self):
        self.freq = collections.defaultdict(int)
        self.counts = collections.defaultdict(list)
        self.max_freq = 0

    def push(self, x: int) -> None:
        new_freq = self.freq[x] + 1
        self.freq[x] = new_freq
        self.counts[new_freq].append(x)
        self.max_freq = max(self.max_freq, new_freq)

    def pop(self) -> int:
        nums = self.counts[self.max_freq]
        x = nums.pop()
        self.freq[x] -= 1
        if len(nums) == 0:
            self.max_freq -= 1
        return x


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()