最大频率栈

题目描述
设计一个基于哈希的栈，称为“频率栈”，它支持两种操作：

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

你需要实现 FreqStack 类：

• FreqStack() 初始化一个空的频率栈。
• void push(int val) 将一个元素 val 推入栈中。
• int pop() 弹出并返回频率最高的元素（规则如上）。

示例

输入：
["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 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 出现频率最高（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. 理解问题核心
我们需要一个数据结构，能快速回答“当前哪个元素频率最高？如果并列，哪个最近被推入？”。

• 频率最高：需要追踪每个值的出现次数。
• 最近推入：需要记录同一频率的所有值，且按推入顺序排列（栈的特性，后进先出）。

2. 选择数据结构

• 哈希表 freq：键是元素值 val，值是该元素到当前为止的出现次数。
• 哈希表 group：键是频率 freq，值是一个栈，保存所有达到这个频率的元素（按推入顺序）。
  例如，当某个元素第一次出现时，频率为1，它进入 group[1] 的栈；当它第二次出现，频率变为2，它又进入 group[2] 的栈。
• 变量 maxFreq：记录当前全局最大频率，用于快速定位 group 中该弹出哪个栈。

3. 操作步骤

push(val) 操作：

1. 更新该元素的频率：freq[val] += 1，得到新的频率 f。
2. 更新全局最大频率：maxFreq = max(maxFreq, f)。
3. 将 val 推入 group[f] 对应的栈中。
   注意：同一个 val 会在多个频率的栈中出现（比如频率1、2、3的栈中都有它），这保证了当它被弹出后，下一层频率的栈中还有它。

pop() 操作：

1. 从 group[maxFreq] 的栈顶弹出元素 x（这就是当前频率最高且最近推入的元素）。
2. 更新该元素的频率：freq[x] -= 1。
3. 如果 group[maxFreq] 的栈为空，说明当前最大频率已无元素，将 maxFreq -= 1。
4. 返回 x。

4. 举例推演
以题目示例为例，初始状态：
freq = {}, group = {}, maxFreq = 0。

1. push(5):

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

2. push(7):

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

3. push(5):

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

4. push(7):

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

5. push(4):

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

6. push(5):

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

7. pop():

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

8. pop():

   • 从 group[2] 弹出 7（栈顶是7）。
   • freq[7] = 1，group[2] 变为 [5]（不空，maxFreq 仍为2）。
   • 返回 7。

9. pop():

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

10. pop():

    • 从 group[1] 弹出 4（栈顶是4）。
    • freq[4] = 0，group[1] 变为 [5, 7]（不空）。
    • 返回 4。

5. 时间复杂度与空间复杂度

• push 和 pop 都是 O(1) 时间操作（哈希表与栈操作均为常数时间）。
• 空间复杂度：O(n)，n 为推入元素的总次数（每个元素会在多个频率栈中出现一次）。

6. 关键点总结

• 核心思想是“将相同频率的元素用栈组织”，这样自然满足“同频率时取最近推入”的条件。
• maxFreq 的维护保证了能快速找到最高频率对应的栈。
• 同一个元素存在于多个频率栈中，模拟了它在不同频率级别的“存在状态”，使得弹出后能正确降级到下一频率。