力扣-895. 最大频率栈

题目描述

思路及实现

借助Counter类及其方法

这是我一开始想到的思路，毕竟是python，能借就借嘛。Counter就能够统计每个元素出现的次数，而most_common方法又能够把频率最高的找出来，这不就显而易见出答案了嘛~

class FreqStack:

    def __init__(self):
        self.stack = list()  # 栈
        self.cnt = Counter()  # 保存出现频率

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.cnt[val] += 1

    def pop(self) -> int:
        tmp_list = self.cnt.most_common()
        num_list = []
        frequecy = tmp_list[0][1]
        for t in tmp_list:  # 找出所有频率相同的数
            if t[1] == frequecy:
                num_list.append(t[0])
            else:
                break
        for i in range(len(self.stack) - 1, -1, -1):
            if self.stack[i] in num_list:
                self.cnt[self.stack[i]] -= 1
                return self.stack.pop(i)

OK，超时了，很符合我对偷懒下场的想象。那就只好另起炉灶了。

依旧借助Counter类，但是利用频率栈

思路来源：灵神

class FreqStack:

    def __init__(self):
        self.stacks: List[List[int]] = list()  # 频率栈的列表
        self.cnt: Counter = Counter()  # 保存出现频率

    def push(self, val: int) -> None:
        if self.cnt[val] == len(self.stacks):  # 出现新的最大频率，新建频率栈
            self.stacks.append([val])
        else:  # 已有这种频率的频率栈，直接加入
            self.stacks[self.cnt[val]].append(val)
        self.cnt[val] += 1  # 最后更新频率，就能避免1对上0的情况

    def pop(self) -> int:
        val = self.stacks[-1].pop()  # 取最高频率栈栈顶的数
        if not self.stacks[-1]:  # 最高频率栈空了，先删掉，下次有数再创建回来，防止空操作
            self.stacks.pop()
        self.cnt[val] -= 1  # 更新频率
        return val

希望本文章能够帮到您~