哈希算法题目：哈希表在解决“最大频率栈”问题中的应用

题目描述
你需要实现一个“频率栈”数据结构，支持以下操作：

• push(val)：将整数 val 推入栈中。
• pop()：弹出并返回栈中出现频率最高的元素。如果频率最高的元素不唯一，则返回最近被推入的那个元素（即满足最高频率的、最靠近栈顶的元素）。

举例

freqStack = 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 出现 3 次（最高频），栈: [5,7,5,7,4]
freqStack.pop()   # 返回 7，因为 5 和 7 都出现 2 次，但 7 是最近推入的，栈: [5,7,5,4]
freqStack.pop()   # 返回 5，栈: [5,7,4]
freqStack.pop()   # 返回 4，栈: [5,7]

逐步解题过程

第一步：理解需求与难点

• 需要快速获取当前“频率最高的元素”，若有多个相同最高频率的元素，需知道它们被推入的顺序，以便弹出“最近”的那个。
• 不能简单用单个最大堆，因为“最近推入”的顺序在弹出后会动态变化。

第二步：核心数据结构设计
使用三个关键部分：

1. 频率表（freq字典）

   • 键：元素值 val。
   • 值：该元素当前的出现频率。
   • 用途：快速知道一个元素的当前频率。

2. 分组栈（group字典）

   • 键：频率值（整数）。
   • 值：一个列表（栈），按推入顺序存放所有达到该频率的元素。
   • 举例：当元素 5 第 1 次出现时，它会被放入 group[1] 的栈中；当它第 2 次出现时，又会被放入 group[2] 的栈中。
   • 用途：对同一频率的所有元素，其入栈顺序自然被保留，栈顶就是该频率下“最近推入”的元素。

3. 当前最大频率（maxFreq）

   • 一个整数，记录全局最高频率，确保 pop() 时能快速定位到 group[maxFreq] 栈。

第三步：操作步骤详解

push(val) 操作

1. 更新 freq[val] += 1（若 val 不存在则初始化为 0 再加 1）。得到新频率 f。
2. 将 val 推入 group[f] 对应的栈中（若 group[f] 不存在则创建一个空栈）。
3. 更新 maxFreq = max(maxFreq, f)。

为什么放入 group[f] 而不是 group[f-1]？
因为 f 是当前该元素出现的总次数，而 group[f] 存储的是“在达到频率 f 的那一刻的元素”。这样，当需要弹出频率为 f 的元素时，直接从 group[f] 栈顶取即可。

pop() 操作

1. 从 group[maxFreq] 栈中弹出栈顶元素 x。
2. 将 freq[x] -= 1（因为该元素被移出了一个，所以频率减少 1）。
3. 如果 group[maxFreq] 栈为空，则 maxFreq -= 1。
4. 返回 x。

第四步：手动模拟示例
初始化：freq = {}, group = {}, maxFreq = 0。

1. push(5)

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

2. push(7)

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

3. push(5)

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

4. push(7)

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

5. push(4)

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

6. push(5)

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

7. pop()

   • 从 group[3] 弹出 5，group[3] 变空。
   • freq[5] = 2
   • maxFreq 降为 2（因为 group[3] 空）。
   • 返回 5。

8. pop()

   • 从 group[2] 弹出栈顶 7。
   • freq[7] = 1
   • group[2] 还剩 [5]，不空，所以 maxFreq 仍为 2。
   • 返回 7。

… 以此类推，符合预期结果。

第五步：复杂度分析

• 时间复杂度：push 和 pop 都是 O(1)。
• 空间复杂度：O(N)，N 为推入元素的总次数。

第六步：关键点总结

1. 利用“分组栈”将相同频率的元素按推入顺序组织，栈顶即最近推入的元素。
2. 维护 maxFreq 避免每次弹出时扫描所有频率。
3. 该设计本质上是哈希表（字典）的嵌套使用，外层键是频率，内层是栈，实现频率与顺序的分离管理。