链接： 最大频率栈
题意：实现一个数据结构，可以像栈一样压入数据，和弹出元素 。特点在于弹出的元素是数据结构内频率（频数）最高的元素，如果最高频率的元素有多个，弹出最后压入的。
使用一个全局变量max_feq来记录当前最大的频率，使用一个字典freq记录每个元素的频率，使用一个字典group来记录每个频率有哪些元素已经push的顺序。
push val
- 从freq中查找val的频率，并加1，作为val的新频率f
- 使用val的新频率，更新freq[val]=f
- 判断val的新频率f是否大于max_freq，如果大于，max_freq自增1
- 更新字典group，将val插入到group[f]这个栈的顶部
pop
- 根据max_freq找到具有最大频率元素构成的栈，并将栈顶元素出栈
- 在freq字典中，将出栈元素的频率减1
- 如果max_freq对应的栈为空，将最大频率max_freq减1
- 返回出栈元素
这个数据结构有如下特性：
- max_freq不会跳跃，随着不断插入数据，max_freq最多比之前加1
- 如果某个元素val的频率为f，则在group字典中，key = 1,2,...,f对应的栈中都有且只有一个val
class FreqStack:
def __init__(self):
self.freq = dict()
self.group = dict()
self.max_freq = 0
def push(self, val: int) -> None:
f = self.freq.get(val, 0) + 1
self.freq[val] = f
if f > self.max_freq:
self.max_freq += 1
if f in self.group:
self.group[f].append(val)
else:
self.group[f] = [val]
def pop(self) -> int:
val = self.group[self.max_freq].pop()
self.freq[val] -= 1
if not self.group[self.max_freq]:
self.max_freq -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
