1. 最大频率栈问题解析第一次看到LeetCode 895这道题时我正喝着咖啡准备开始一天的刷题。题目描述很简单设计一个类似栈的数据结构但pop操作需要返回出现频率最高的元素。如果多个元素频率相同就返回最靠近栈顶的那个。我的第一反应是——这不就是给普通栈加了个统计员吗1.1 问题核心需求这个数据结构需要支持两个操作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次其他最多2次→栈[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 为什么这是个困难题这道题被标记为困难有几个原因需要同时维护频率信息和入栈顺序常规栈结构无法直接满足需求需要设计高效的数据结构组合时间复杂度要求O(1)我在白板上画了半小时才理清思路——原来需要三个核心组件频率计数器哈希表记录每个值的出现次数频率到元素栈的映射相同频率的元素按入栈顺序保存当前最大频率值快速定位要弹出的元素2. 数据结构设计与实现2.1 核心数据结构选择经过多次尝试我发现最优解需要以下数据结构组合unordered_mapint, int freq记录每个值的出现频率unordered_mapint, stackint group按频率分组保存元素int maxFreq记录当前最大频率关键点当元素被push时它的频率会增加并被放入对应频率的栈中。pop时直接从maxFreq对应的栈顶取元素。2.2 C实现详解class FreqStack { private: unordered_mapint, int freq; unordered_mapint, stackint group; int maxFreq 0; public: void push(int val) { int f freq[val]; // 更新频率 maxFreq max(maxFreq, f); // 更新最大频率 group[f].push(val); // 放入对应频率栈 } int pop() { int val group[maxFreq].top(); // 获取当前最高频率元素 group[maxFreq].pop(); // 移除该元素 freq[val]--; // 更新频率 // 如果当前频率栈为空降低maxFreq if (group[maxFreq].empty()) { maxFreq--; } return val; } };2.3 时间复杂度分析push操作O(1)哈希表查找和更新O(1)栈操作O(1)pop操作O(1)栈顶访问和弹出O(1)哈希表更新O(1)maxFreq调整O(1)3. 关键问题与解决方案3.1 为什么需要group结构这是我最初设计时踩过的坑。如果只用频率计数器当多个元素频率相同时无法快速确定哪个更靠近栈顶。group结构完美解决了这个问题——每个频率对应一个栈自然保持了入栈顺序。3.2 边界条件处理几个容易出错的场景连续pop导致maxFreq递减的情况相同元素多次push后的频率更新当所有元素频率都为1时的行为退化为普通栈我的测试用例# 测试用例1相同元素多次push stack.push(1) stack.push(1) stack.push(2) assert stack.pop() 1 # 频率2 1 assert stack.pop() 2 # 频率都为12更靠近栈顶 # 测试用例2maxFreq递减 stack.push(3) stack.push(3) stack.push(2) stack.push(2) stack.pop() # 3 (freq2) stack.pop() # 2 (freq2) stack.pop() # 3 (freq1)4. 不同语言实现对比4.1 Java版本特点class FreqStack { private MapInteger, Integer freq; private MapInteger, DequeInteger group; 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); maxFreq Math.max(maxFreq, f); group.computeIfAbsent(f, z-new ArrayDeque()).push(val); } public int pop() { int val group.get(maxFreq).pop(); freq.put(val, freq.get(val)-1); if (group.get(maxFreq).isEmpty()) { maxFreq--; } return val; } }Java注意点使用Deque替代Stack性能更好computeIfAbsent简化group初始化需要处理null的情况getOrDefault4.2 Python实现技巧from collections import defaultdict class FreqStack: def __init__(self): self.freq defaultdict(int) self.group defaultdict(list) self.max_freq 0 def push(self, val: int) - None: self.freq[val] 1 self.max_freq max(self.max_freq, self.freq[val]) self.group[self.freq[val]].append(val) # 用list模拟栈 def pop(self) - int: val self.group[self.max_freq].pop() self.freq[val] - 1 if not self.group[self.max_freq]: self.max_freq - 1 return valPython特色使用defaultdict避免键检查用list的append/pop模拟栈Python中栈通常用list实现不需要显式初始化内部数据结构5. 实际应用场景这种数据结构在以下场景很有价值缓存系统优先淘汰高频访问项推荐系统展示高频交互内容负载均衡路由高频请求到不同服务器数据分析实时统计流数据中的高频元素我在工作中曾用类似结构实现过一个实时热点新闻系统——每当用户点击新闻时调用push展示热点时调用pop效果非常好。6. 常见面试问题根据我的面试经验面试官常会追问如果要求pop返回频率最低的元素怎么修改解决方案维护minFreq并同步更新如果数据量非常大内存放不下怎么办解决方案使用外部存储缓存或近似算法如何扩展支持多线程解决方案对共享变量加锁但会影响性能如果pop需要返回最早入栈的元素怎么处理解决方案额外维护一个时间戳队列7. 优化与变种7.1 空间优化方案当元素频率降低时group中的低频率栈可能永远不会再被访问。可以添加清理逻辑void cleanup(int freq) { if (group[freq].empty()) { group.erase(freq); } }7.2 支持频次阈值实际应用中可能需要只关注高频元素void push(int val, int threshold) { if (freq[val] threshold) { group[freq[val]].push(val); maxFreq max(maxFreq, freq[val]); } }7.3 多维度频率统计扩展支持时间维度频率struct TimestampedVal { int val; time_t timestamp; }; unordered_mapint, stackTimestampedVal timeGroup;8. 刷题建议对于这类设计题我的刷题方法是先理解常规数据结构栈/哈希表的特性在白板上画出操作流程编写测试用例验证边界条件思考时间/空间复杂度尝试不同语言的实现这道题在LeetCode周赛中出现过多次变种建议把相关题目都练习一遍LFU CacheAll Oone Data StructureInsert Delete GetRandom O(1)
