哈希算法题目：最大频率栈

字数 1916 2025-11-01 09:19:03

哈希算法题目：最大频率栈

题目描述
设计一个最大频率栈 FreqStack，它需要支持以下操作：

push(int val)：将整数 val 压入栈顶。
int pop()：移除并返回栈中出现频率最高的元素。如果频率最高的元素不止一个，则返回最接近栈顶的那个。

要求
所有操作的时间复杂度应为 O(1)。

解题过程循序渐进讲解

步骤1：理解问题核心
题目要求实现一个“最大频率栈”，其特殊之处在于：

普通栈的 pop 总是返回最后压入的元素（LIFO）；
而最大频率栈的 pop 返回的是当前频率最高的元素，频率相同时再按 LIFO 顺序返回最近压入的那个。

例如：

push(5), push(7), push(5), push(7), push(4), push(5)

此时频率：5 出现 3 次，7 出现 2 次，4 出现 1 次。
第一次 pop 应返回 5（频率最高）。
弹出 5 后，频率变为：5 出现 2 次，7 出现 2 次，4 出现 1 次。
第二次 pop 应返回 7（虽然 5 和 7 频率相同，但 7 更接近栈顶）。

步骤2：数据结构设计思路
要实现 O(1) 的 push 和 pop，需要精心设计数据结构。我们需要记录：

每个值的当前频率（用哈希表 freq 记录：值 → 频率）。
每个频率对应的所有值，且这些值要按压入时间顺序保存（用哈希表 group 记录：频率 → 栈）。
- 例如 group[f] 是一个栈，保存所有当前频率为 f 的值，栈顶是最后压入的那个。
当前最大频率 maxFreq，用于快速确定 pop 时从哪个频率的栈中取元素。

步骤3：详细操作流程

push(val) 操作：

将 val 的频率增加 1：freq[val] += 1（如果 val 未出现过，初始频率为 0）。
获取新的频率 f = freq[val]。
将 val 压入 group[f] 栈中（如果 group[f] 不存在则先创建栈）。
更新 maxFreq = max(maxFreq, f)。

pop() 操作：

从 group[maxFreq] 栈中弹出栈顶元素 x。
将 freq[x] 减 1（因为弹出了一个 x）。
如果 group[maxFreq] 栈为空，则 maxFreq -= 1（因为当前最大频率对应的元素已全部弹出）。
返回 x。

步骤4：示例推演
以输入序列 push(5), push(7), push(5), push(7), push(4), push(5) 为例：

初始状态：
freq = {}, group = {}, maxFreq = 0

push(5)：

freq[5] = 1
group[1] = [5]
maxFreq = 1

push(7)：

freq[7] = 1
group[1] = [5, 7]
maxFreq = 1

push(5)：

freq[5] = 2
group[2] = [5]
maxFreq = 2

push(7)：

freq[7] = 2
group[2] = [5, 7]
maxFreq = 2

push(4)：

freq[4] = 1
group[1] = [5, 7, 4]
maxFreq = 2

push(5)：

freq[5] = 3
group[3] = [5]
maxFreq = 3

pop()：

从 group[3] 弹出 5 → freq[5] = 2，group[3] 为空，maxFreq = 2
返回 5

pop()：

从 group[2] 弹出 7 → freq[7] = 1，group[2] 还剩 [5]，maxFreq = 2
返回 7

pop()：

从 group[2] 弹出 5 → freq[5] = 1，group[2] 为空，maxFreq = 1
返回 5

pop()：

从 group[1] 弹出 4 → freq[4] = 0，group[1] 还剩 [5, 7]，maxFreq = 1
返回 4

步骤5：复杂度分析

push 和 pop 操作只涉及哈希表的查询、更新和栈的压入弹出，都是 O(1) 操作。
空间复杂度：O(n)，n 为压入元素的总数。

关键点：

group[f] 栈保证了同频率元素按 LIFO 顺序弹出。
maxFreq 确保每次都能快速定位到最高频率的栈。

通过以上设计，我们高效地实现了最大频率栈的所有操作。

哈希算法题目：最大频率栈题目描述设计一个最大频率栈 FreqStack ，它需要支持以下操作： push(int val) ：将整数 val 压入栈顶。 int pop() ：移除并返回栈中出现频率最高的元素。如果频率最高的元素不止一个，则返回最接近栈顶的那个。要求所有操作的时间复杂度应为 O(1)。解题过程循序渐进讲解步骤1：理解问题核心题目要求实现一个“最大频率栈”，其特殊之处在于：普通栈的 pop 总是返回最后压入的元素（LIFO）；而最大频率栈的 pop 返回的是当前频率最高的元素，频率相同时再按 LIFO 顺序返回最近压入的那个。例如：此时频率：5 出现 3 次，7 出现 2 次，4 出现 1 次。第一次 pop 应返回 5（频率最高）。弹出 5 后，频率变为：5 出现 2 次，7 出现 2 次，4 出现 1 次。第二次 pop 应返回 7（虽然 5 和 7 频率相同，但 7 更接近栈顶）。步骤2：数据结构设计思路要实现 O(1) 的 push 和 pop ，需要精心设计数据结构。我们需要记录：每个值的当前频率（用哈希表 freq 记录：值 → 频率）。每个频率对应的所有值，且这些值要按压入时间顺序保存（用哈希表 group 记录：频率 → 栈）。例如 group[f] 是一个栈，保存所有当前频率为 f 的值，栈顶是最后压入的那个。当前最大频率 maxFreq ，用于快速确定 pop 时从哪个频率的栈中取元素。步骤3：详细操作流程 push(val) 操作：将 val 的频率增加 1： freq[val] += 1 （如果 val 未出现过，初始频率为 0）。获取新的频率 f = freq[val] 。将 val 压入 group[f] 栈中（如果 group[f] 不存在则先创建栈）。更新 maxFreq = max(maxFreq, f) 。 pop() 操作：从 group[maxFreq] 栈中弹出栈顶元素 x 。将 freq[x] 减 1（因为弹出了一个 x ）。如果 group[maxFreq] 栈为空，则 maxFreq -= 1 （因为当前最大频率对应的元素已全部弹出）。返回 x 。步骤4：示例推演以输入序列 push(5), push(7), push(5), push(7), push(4), push(5) 为例：初始状态： freq = {} , group = {} , maxFreq = 0 push(5) ： freq[5] = 1 group[1] = [5] maxFreq = 1 push(7) ： freq[7] = 1 group[1] = [5, 7] maxFreq = 1 push(5) ： freq[5] = 2 group[2] = [5] maxFreq = 2 push(7) ： freq[7] = 2 group[2] = [5, 7] maxFreq = 2 push(4) ： freq[4] = 1 group[1] = [5, 7, 4] maxFreq = 2 push(5) ： freq[5] = 3 group[3] = [5] maxFreq = 3 pop() ：从 group[3] 弹出 5 → freq[5] = 2 ， group[3] 为空， maxFreq = 2 返回 5 pop() ：从 group[2] 弹出 7 → freq[7] = 1 ， group[2] 还剩 [ 5]， maxFreq = 2 返回 7 pop() ：从 group[2] 弹出 5 → freq[5] = 1 ， group[2] 为空， maxFreq = 1 返回 5 pop() ：从 group[1] 弹出 4 → freq[4] = 0 ， group[1] 还剩 [ 5, 7]， maxFreq = 1 返回 4 步骤5：复杂度分析 push 和 pop 操作只涉及哈希表的查询、更新和栈的压入弹出，都是 O(1) 操作。空间复杂度：O(n)，n 为压入元素的总数。关键点： group[f] 栈保证了同频率元素按 LIFO 顺序弹出。 maxFreq 确保每次都能快速定位到最高频率的栈。通过以上设计，我们高效地实现了最大频率栈的所有操作。