*895-最大频率栈

题目

895. 最大频率栈

要求

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

FreqStack 有两个函数：

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

• pop()，它移除并返回栈中出现最频繁的元素. 如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

思路

对于每个元素, 建立一个元素到频率的映射表. 由于我们关系最大频率, 还需要特别记录当前的最大频率.

巧妙的一点是这里虽然实现的是最大频率栈, 但实际上并不是用栈来实现的. 而是使用一个group, group也是一个映射, 是频率到该频率对应的元素列表. 例如元素1的频率为3, 则group[1], group[2], group[3]对应的列表中都有1.

以上的方法考虑到pop方法的要求: 如果最频繁的元素不只一个, 则移除并返回最接近栈顶的元素. 这样在同一频率下, 后出现的, 更靠近实际栈顶的会出现在列表的后面.

代码

class FreqStack(object):

    def __init__(self):
        self.freq = collections.Counter()
        self.group = collections.defaultdict(list)
        self.max_freq = 0

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        f = self.freq[x] + 1
        self.freq[x] = f
        if f > self.max_freq:
            self.max_freq = f
        self.group[f].append(x)

    def pop(self):
        """
        :rtype: int
        """
        t = self.group[self.max_freq].pop(-1)
        self.freq[t] -= 1
        if len(self.group[self.max_freq]) == 0:
            self.max_freq -= 1
        return t