0895. Maximum Frequency Stack¶
题目信息¶
- 题号:
0895
- 难度:
Hard
- 主题:
设计题、频率统计、最近优先
- 原题:
- 重点:
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,之后结构为空。