LeetCode 895：最大频率栈

LeetCode 895：最大频率栈

问题定义与核心挑战

设计一个栈结构，支持两种操作：

• push(val)：将元素压入栈顶。
• pop()：弹出频率最高的元素；若多个元素频率相同，弹出最接近栈顶（最后压入）的元素。

核心挑战：如何高效维护元素的频率和压入顺序，确保 pop 操作的时间复杂度为 O(1)。

核心思路：频率分组 + 栈结构

通过 两个哈希表 和 一个最大值跟踪变量 实现：

1. 频率映射（freq）：记录每个元素的当前频率。
2. 频率分组（group）：按频率分组，每个频率对应一个栈，保存该频率下的元素（按压入顺序，栈顶为最后压入的元素）。
3. 最大频率（maxFreq）：跟踪当前所有元素的最大频率，快速定位 pop 的目标组。

算法步骤详解

1. 数据结构初始化

class FreqStack {
    private Map<Integer, Integer> freq;         // 记录元素的频率：val → 频率
    private Map<Integer, Stack<Integer>> group; // 按频率分组：频率 → 元素栈（保存压入顺序）
    private int maxFreq;                        // 当前最大频率

    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxFreq = 0;
    }
}

2. push 操作：更新频率与分组

当压入元素 val 时：

• 步骤1：更新频率：val 的频率加1，得到新频率 f。
• 步骤2：分组存储：将 val 压入 group[f] 对应的栈（若栈不存在则新建）。
• 步骤3：更新最大频率：若 f 大于当前 maxFreq，则更新 maxFreq。

public void push(int val) {
    // 1. 更新频率
    int f = freq.getOrDefault(val, 0) + 1;
    freq.put(val, f);

    // 2. 存入对应频率的栈（懒创建）
    group.putIfAbsent(f, new Stack<>());
    group.get(f).push(val);

    // 3. 更新最大频率
    if (f > maxFreq) {
        maxFreq = f;
    }
}

3. pop 操作：弹出最高频率的最近元素

当弹出元素时：

• 步骤1：定位目标栈：从 group[maxFreq] 中获取当前最高频率的栈。
• 步骤2：弹出栈顶元素：该元素是同频率下最后压入的（最接近栈顶）。
• 步骤3：更新频率：将该元素的频率减1。
• 步骤4：更新最大频率：若目标栈为空，说明当前最大频率的元素已耗尽，maxFreq 减1。

public int pop() {
    // 1. 从最高频率的栈中弹出元素
    Stack<Integer> stack = group.get(maxFreq);
    int val = stack.pop();

    // 2. 更新频率
    freq.put(val, freq.get(val) - 1);

    // 3. 若栈为空，降低最大频率
    if (stack.isEmpty()) {
        maxFreq--;
    }

    return val;
}

算法复杂度分析

• 时间复杂度：

  • push：哈希表操作和栈压入均为 O(1)。
  • pop：哈希表操作和栈弹出均为 O(1)。
    因此，所有操作的时间复杂度为 O(1)。

• 空间复杂度：
  哈希表和栈存储所有元素，空间复杂度为 O(n)（n 为总元素数）。

示例验证（以题目示例1为例）

输入操作：push(5)、push(7)、push(5)、push(7)、push(4)、push(5)、pop()、pop()、pop()、pop()

过程模拟：

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，freq[5]=2，栈空 → maxFreq=2。返回 5。
8. pop()：
   • 从 group[2] 弹出 7，freq[7]=1，栈剩 [5] → maxFreq=2。返回 7。
9. pop()：
   • 从 group[2] 弹出 5，freq[5]=1，栈空 → maxFreq=1。返回 5。
10. pop()：
    • 从 group[1] 弹出 4，freq[4]=0，栈剩 [5,7] → maxFreq=1。返回 4。

输出与题目示例一致：5,7,5,4。

完整代码

import java.util.HashMap;
import java.util.Stack;

class FreqStack {
    private Map<Integer, Integer> freq;         // val -> 出现次数
    private Map<Integer, Stack<Integer>> group; // 次数 -> 对应元素的栈（按push顺序）
    private int maxFreq;                        // 当前最大次数

    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int val) {
        // 更新频率
        int f = freq.getOrDefault(val, 0) + 1;
        freq.put(val, f);

        // 存入对应次数的栈（懒加载创建栈）
        group.putIfAbsent(f, new Stack<>());
        group.get(f).push(val);

        // 更新最大频率
        if (f > maxFreq) {
            maxFreq = f;
        }
    }

    public int pop() {
        // 从当前最大频率的栈中弹出元素
        Stack<Integer> stack = group.get(maxFreq);
        int val = stack.pop();

        // 更新频率
        freq.put(val, freq.get(val) - 1);

        // 若栈为空，降低最大频率
        if (stack.isEmpty()) {
            maxFreq--;
        }

        return val;
    }
}

总结

该方案通过 频率分组 + 栈结构 巧妙解决了“最高频率优先，同频率近栈顶优先”的需求，确保了所有操作的 O(1) 时间复杂度，高效且易理解。核心思想是利用哈希表维护频率关系，栈维护同频率下的顺序，是处理“频率 + 顺序”类问题的经典思路。