题目描述

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

-push(int x), which pushes an integer x onto the stack.
-pop(), which removes删除 and returns 返回 the most frequent最大频率 element的元素 in the stack.
If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

模拟栈，返回频率最多元素

Python 代码

class FreqStack:

    def __init__(self): #定义一下这个类。一共有三个attribute -①freq -②group -③maxfreq
        self.freq = collections.Counter() #这个存(字符串/词)出现的频率
        self.group = collections.defaultdict(list)
        self.maxfreq = 0

    def push(self, x: int) -> None:
        f = self.freq[x] + 1
        self.freq[x] = f
        if f > self.maxfreq: self.maxfreq = f #当f比最大频率大时，更新最大频率
        self.group[f].append(x) #把x加入group中

    def pop(self) -> int:
        x = self.group[self.maxfreq].pop() #defaultdict(list)支持直接pop操作
        self.freq[x] -= 1 #弹出后把x的频率计数-1
        if not self.group[self.maxfreq]: self.maxfreq -= 1 #如果group的第最大频率不是空，那就把它减一
        return x #按题意返回x (最大频率的词)