LeetCode 题解工作台
最大频率栈
设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出 出现频率 最高的元素。 实现 FreqStack 类: FreqStack() 构造一个空的堆栈。 void push(int val) 将一个整数 val 压入栈顶。 int pop() 删除并返回堆栈中出现频率最高的元素。 如果出现频率…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
根据题目描述，我们需要设计一个支持弹出“出现频率最高”的元素的数据结构。如果存在多个元素出现频率相同，那么弹出最接近栈顶的元素。 我们可以使用哈希表 记录每个元素出现的频率，用一个优先队列（大根堆） 维护元素频率以及对应的压栈时间戳。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:
FreqStack()构造一个空的堆栈。void push(int val)将一个整数val压入栈顶。int pop()删除并返回堆栈中出现频率最高的元素。- 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
示例 1：
输入： ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] 输出：[null,null,null,null,null,null,null,5,7,5,4] 解释： FreqStack = new FreqStack(); freqStack.push (5);//堆栈为 [5] freqStack.push (7);//堆栈是 [5,7] freqStack.push (5);//堆栈是 [5,7,5] freqStack.push (7);//堆栈是 [5,7,5,7] freqStack.push (4);//堆栈是 [5,7,5,7,4] freqStack.push (5);//堆栈是 [5,7,5,7,4,5] freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。 freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。 freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。 freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。
提示：
0 <= val <= 109push和pop的操作数不大于2 * 104。- 输入保证在调用
pop之前堆栈中至少有一个元素。
解题思路
方法一：哈希表 + 优先队列（大根堆）
根据题目描述，我们需要设计一个支持弹出“出现频率最高”的元素的数据结构。如果存在多个元素出现频率相同，那么弹出最接近栈顶的元素。
我们可以使用哈希表 记录每个元素出现的频率，用一个优先队列（大根堆） 维护元素频率以及对应的压栈时间戳。
执行压栈操作时，我们先将当前时间戳加一，即 ；然后将元素 的频率加一，即 ，最后将三元组 加入优先队列 中。压栈操作的时间复杂度为 。
执行弹栈操作时，我们直接从优先队列 中弹出一个元素即可。由于优先队列 中的元素按照频率降序排序，因此弹出的元素一定是出现频率最高的元素。如果存在多个元素出现频率相同，那么弹出最接近栈顶的元素，即弹出时间戳最大的元素。弹出后，我们将弹出元素的频率减一，即 。弹栈操作的时间复杂度为 。
class FreqStack:
def __init__(self):
self.cnt = defaultdict(int)
self.q = []
self.ts = 0
def push(self, val: int) -> None:
self.ts += 1
self.cnt[val] += 1
heappush(self.q, (-self.cnt[val], -self.ts, val))
def pop(self) -> int:
val = heappop(self.q)[2]
self.cnt[val] -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assess how well the candidate manages stack-based state manipulation and tracking element frequencies.
- question_mark
Evaluate the candidate's ability to optimize the problem considering both time and space constraints.
- question_mark
Test if the candidate can balance simplicity with efficiency, especially when managing large numbers of operations.
常见陷阱
外企场景- error
Failing to manage the frequency of elements efficiently can lead to suboptimal performance.
- error
Not correctly handling edge cases where multiple elements have the same frequency.
- error
Overcomplicating the solution by using overly complex data structures when a simpler one will suffice.
进阶变体
外企场景- arrow_right_alt
Allowing multiple elements with the same frequency and managing the frequency stack differently.
- arrow_right_alt
Implementing a solution that supports different stack management strategies, like using a priority queue.
- arrow_right_alt
Optimizing for a different performance trade-off, such as focusing more on time complexity over space.