0895. Maximum Frequency Stack

题目信息

题号:

0895

难度:

Hard

主题:

设计题、频率统计、最近优先

原题:

LeetCode 0895

重点:

pop 删除当前出现频率最高的值;最高频率并列时删除其中最近一次被压入的值,对象状态跨调用保留

题目重述

实现 FreqStack 类,维护一个按压入历史变化的栈式结构,对象需要在多次方法调用之间持续保存当前尚未删除的元素实例。

push(val):把一个值为 val 的新元素压入结构。同一个数值可以被多次压入,每次都是独立实例。

pop():找出当前剩余实例中出现频率最高的数值,删除并返回它的一个实例。若多个数值频率并列,返回这些值中最靠近当前栈顶、也就是最近一次被压入的那个。调用时保证结构非空。

0 <= val <= 10^9,push 和 pop 的总调用次数不超过 2 * 10^4。

自建示例

最高频值变化后再按最近顺序打破平局:

输入:
操作 = ["FreqStack","push","push","push","push","push","push","pop","pop","pop"]
参数 = [[],[4],[6],[4],[7],[6],[6],[],[],[]]
输出:[null,null,null,null,null,null,null,6,6,4]
解释:第一次弹出前,6 出现三次,是唯一最高频值;移除最近的 6 后,4 与 6 都出现两次,但 6 的剩余最近实例比 4 更靠近栈顶,因此第二次仍返回 6;随后 4 出现两次,第三次返回 4。

结构中只有一个元素:

输入:
操作 = ["FreqStack","push","pop"]
参数 = [[],[9],[]]
输出:[null,null,9]
解释:唯一元素 9 的频率最高且也最靠近栈顶,因此 pop 必须返回 9,之后结构为空。