当前位置：首页 > ds >正文

LeetCode 895：最大频率栈

ds 2025/7/27 14:25:22

LeetCode 895：最大频率栈

在这里插入图片描述

问题定义与核心挑战

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

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

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

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

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

频率映射（freq）：记录每个元素的当前频率。
频率分组（group）：按频率分组，每个频率对应一个栈，保存该频率下的元素（按压入顺序，栈顶为最后压入的元素）。
最大频率（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()

过程模拟：

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，栈空 → maxFreq=2。返回 5。
pop()：
- 从 group[2] 弹出 7，freq[7]=1，栈剩 [5] → maxFreq=2。返回 7。
pop()：
- 从 group[2] 弹出 5，freq[5]=1，栈空 → maxFreq=1。返回 5。
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;}
}