刷 LeetCode 的时候895 这道“最大频率栈”我印象特别深。题目本身不长核心就是让你实现一个类有public void push(int val)和public int pop()两个方法但要求 pop 返回的是当前频率最高、且最靠近栈顶的那个元素。要是频率并列最高就返回“后 push 进去的那个”。我没有急着写代码先试着用 Kimi 把思路捋了一遍发现这题表面是栈本质上考的是“如何用多个基础数据结构组合出新的语义”。这篇文章就把我完整的思考过程、实现细节、踩坑记录和借助 AI 辅助刷题的心得都整理出来希望能帮你少走弯路。1. 题目与整体思路拆解1.1 原题到底在说什么先复述一下题目避免看一半忘了我们在聊什么。你需要实现一个FreqStack类里面有push(int val)把一个整数推入栈中。pop()移除并返回栈中出现频率最高的元素。如果频率最高的元素不止一个则返回“最靠近栈顶”的那个也就是最后被 push 进去的那个。注意这里的“栈”不是传统意义上只能从栈顶进出。它更像是一个带规则的集合插入时正常尾插但删除时按“频率优先 后进先出”的规则来。举个例子依次执行FreqStack stack new FreqStack(); stack.push(5); // 栈[5] stack.push(7); // 栈[5,7] stack.push(5); // 栈[5,7,5] stack.push(7); // 栈[5,7,5,7] stack.push(4); // 栈[5,7,5,7,4] stack.push(5); // 栈[5,7,5,7,4,5] stack.pop(); // 返回 5因为 5 出现 3 次7 出现 2 次4 出现 1 次 stack.pop(); // 返回 7因为 5 和 7 都出现 2 次但 7 更靠近栈顶 stack.pop(); // 返回 5因为 5 出现 2 次7 出现 1 次这个例子我后来照着跑了很多遍基本上把规则解释清楚了每次 pop 都要看“全局频率”而不是只看栈顶。1.2 为什么第一反应会觉得难很多人的第一反应是我用一个HashMap记录每个元素出现次数然后每次 pop 的时候遍历一遍所有元素找出频率最高的那个返回。这个方法逻辑上没问题但问题在于时间复杂度是 O(n)题目要求 pop 也要 O(1)数据一大就直接超时。第二个常见思路是用优先队列最大堆把元素按频率加入时间排序。这个思路方向是对的但同样存在问题当你 push 一个新元素时这个元素之前的“频率”变了优先队列里旧条目还在删除和更新很麻烦需要额外维护失效标记实现起来并不直观。第三个思路是直接把“栈”本身改造成一个“支持插入时统计、删除时按最大频率弹出”的结构。这一步就回到了核心难题如何在 O(1) 时间内知道当前哪个元素频率最高并且知道同频元素中谁最靠近栈顶。1.3 核心突破用“频率分组”替代“全局排序”我卡在这里的时候去问了 Kimi它给了一个很关键的点不要把元素按照“值”去组织而是按照“频率”去分组。具体来说维护两个哈希表freq记录每个值当前出现的次数。group记录每个频率对应的元素“栈”。然后维护一个全局变量maxFreq表示当前所有元素中的最大频率。push 的时候更新freq[val]拿到新的频率 f。把 val 放进group[f]这个栈里。更新maxFreq max(maxFreq, f)。pop 的时候从group[maxFreq]的栈顶取出元素 val。把freq[val]--。如果group[maxFreq]为空maxFreq--。返回 val。我当时看到这个思路的第一反应是“妙”但第二反应是“为什么这样就是对的”后来想明白了freq[val]是全局频率group[f]里存的就是所有“当前频率恰好为 f”的元素并且它们的顺序就是这些元素最后一次到达该频率的顺序。所以从group[maxFreq]栈顶取值既能保证频率最高又能保证“后 push 的优先”。这就像把所有元素按“等级频率”分成了好多排队伍每一排内部按“先来后到”排队。pop 的时候永远先处理最高等级队伍里最后一个报到的成员。2. 核心细节解析与实操要点2.1 push 的完整流程与代码我用 Java 实现了第一版代码如下class FreqStack { MapInteger, Integer freq; MapInteger, DequeInteger group; 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 ArrayDeque()); group.get(f).push(val); maxFreq Math.max(maxFreq, f); } public int pop() { int val group.get(maxFreq).pop(); freq.put(val, freq.get(val) - 1); if (group.get(maxFreq).isEmpty()) { maxFreq--; } return val; } }这段代码看起来很短但有几个值得抠的细节。第一freq用什么容器。我用的是MapInteger, Integerkey 是元素值value 是出现次数。这里有个小坑getOrDefault一定要用因为第一次 push 的时候这个值还没出现过。如果你先get再判空代码会很啰嗦而且容易漏掉null判断。第二group用MapInteger, DequeInteger。这里Deque可以选择ArrayDeque也可以选LinkedList都能实现栈的功能。我个人喜欢ArrayDeque因为它底层是数组访问连续内存更快在 LeetCode 上跑起来也更稳。不过如果你习惯用Stack类也可以只是面试时我一般不用Stack因为它的并发方法有锁开销而且继承自Vector性能上没什么优势。第三maxFreq的更新只会在 push 时增加在 pop 时减少。push 阶段直接取Math.max(maxFreq, f)pop 阶段只有当group[maxFreq]为空时才会减少因为此时最高频率的元素已经全部被弹出下一个最高频率必然是maxFreq - 1不会跳变。2.2 pop 的完整流程与代码pop 的代码刚才已经写了但我想再仔细拆一下执行过程中每一行在干什么。第一步group.get(maxFreq).pop()。这一步取出当前最高频率队伍里的栈顶元素也就是最晚进入这一频率的元素。比如maxFreq 3说明当前存在某个元素出现了 3 次group[3]栈里存的可能是[x, y, z]其中 z 是最近一次达到 3 次频率的元素所以它应该被弹出。第二步freq.put(val, freq.get(val) - 1)。注意由于val肯定存在于freq中所以这里可以直接get。这个操作相当于把该元素的全局频率从“3”降到“2”下次它如果再被 push又会重新进入group[3]。第三步检查group[maxFreq]是否为空。如果为空说明当前最大频率下已经没有元素了比如maxFreq 3对应的栈空了说明所有达到过 3 次的元素都被弹出了全局最大频率自然降到 2。但这里有个隐藏逻辑maxFreq减 1 之后group[2]一定不为空吗答案是肯定的因为如果group[3]里有元素说明至少有一个元素曾经达到过 3 次那么它达到 2 次的时候也一定在group[2]里存在过并且还没有被弹出。因为 pop 总是优先弹出更高频率的元素所以低频率队伍一定“攒”着东西。第四步返回val。这一步没啥好说的但要注意返回的val是第二步中已经完成频率递减的元素所以下一次 pop 时它的频率已经变了不会出现“弹出一个元素但它的频率记录还是旧值”的情况。2.3 复杂度与空间分析这两个操作的复杂度都是 O(1)因为无论是freq的get/put还是group的get/put/pop都是基于哈希表和栈的常数级操作。空间方面freq会存所有出现过的不同元素group会把每个元素在每次频率变化时都存一份。比如某个元素出现 5 次它可能出现在group[1]、group[2]、group[3]、group[4]、group[5]里这里说的是 push 过程中它被重复放入不同频率组实际上 push 5 次就会在 5 个组里各出现一次。所以空间复杂度是 O(n)n 是所有 push 操作的总次数。关于这个空间开销很多人会纠结“为什么同一个元素可以出现在多个频率栈里”。我觉得可以这样理解group[f]里保存的不是“当前值为 x 的元素”而是“当前值为 x 的元素在频率为 f 时的入境记录”。每次 push 都是一次新的入境所以同一个值会出现在多个组里。正因为这样pop 后才能通过对栈顶元素的弹出实现“最近到达该频率优先”。2.4 边界情况与隐藏细节实操中我遇到过几个边界情况这里统一列一下空栈调用 pop题目一般保证不会发生但面试时最好主动问清楚。如果不保证代码里需要加if (maxFreq 0) throw new RuntimeException(empty stack)之类的处理。push 重复值很多次比如连续 push 10 次 1。此时maxFreq会一路升到 10group[1]到group[10]都有 1 这个值的记录。pop 会先弹出 1然后maxFreq降到 9再弹出 1再降到 8……这个过程要能顺畅执行不能因为group[9]里的栈为空而出错。不同元素跳到相同频率比如 push 5、push 7、push 5、push 7此时group[2]里会有 5 和 7栈顶是 7pop 时会先返回 7。这个设计完美匹配“同频优先返回最后 push 的”。freq 减到 0 的元素pop 之后freq[val]可能变成 0此时不用从freq中删除留着也没关系因为下次 push 时getOrDefault会拿到 0然后加 1 变成 1。当然为了节省内存也可以删除但不是必须。还有一个隐藏细节group.get(maxFreq).pop()时group.get(maxFreq)一定不为空这是由maxFreq的维护逻辑保证的。但如果你初始maxFreq为 0而group里没有 key 为 0 的栈就需要小心。我的代码里push从 1 开始更新频率所以maxFreq至少是 1pop 时不会访问到 0。这一点如果你把maxFreq初值设为 -1 或者用其他方式维护就要额外小心。3. 借力 Kimi 辅助刷题的真实过程3.1 我是怎么用 Kimi 提问的我一开始完全没思路后来决定用 Kimi 来加速理解。但我没有一上来就说“给我代码”而是尽可能把问题描述清楚。我当时的问题大概是这样的“我在做 LeetCode 895 最大频率栈要求 push O(1)、pop O(1)pop 要返回频率最高且最靠近栈顶的元素。我目前只知道用哈希表记录频率但 pop 的时候怎么快速找到最大频率有没有经典解法请先讲思路不要给代码。”这里的关键是“先要思路不要给代码”。因为一旦看到代码很容易陷入“我记住了但没有真正理解”的状态。Kimi 给出的思路就是我在 1.3 里写的两个哈希表 maxFreq 的做法。我觉得这个提问方式特别适合大多数 LeetCode 题的入门阶段把题目抽象成几个关键约束然后明确告诉 AI 你卡在哪个环节要求它先讲思路。这样你会得到高质量的回答而不是一堆无关的废话。3.2 Kimi 给出的思路与我的验证Kimi 给的思路虽然清晰但我并没有直接拿它当标准答案而是手动跑了一个用例来验证。我用的用例就是题目里的push(5) - freq[5]1, group[1][5], maxFreq1 push(7) - freq[7]1, group[1][5,7], maxFreq1 push(5) - freq[5]2, group[2][5], maxFreq2 push(7) - freq[7]2, group[2][5,7], maxFreq2 push(4) - freq[4]1, group[1][5,7,4], maxFreq2 push(5) - freq[5]3, group[3][5], maxFreq3 pop() - group[3].pop() 5, freq[5]2, group[3]空, maxFreq2 pop() - group[2].pop() 7, freq[7]1, group[2][5], maxFreq2 pop() - group[2].pop() 5, freq[5]1, group[2]空, maxFreq1手动推导完之后我发现这个算法确实是对的。但这个验证过程非常重要因为你不能因为 AI 说“这是对的”就相信必须用自己的推演去确认。我还问了 Kimi 一个追问“为什么 frequency 相同时要返回最后 push 的元素而不是最先进来的”它的回答很简洁因为题目要求“最靠近栈顶”而栈顶就是最后进来的。这个解释其实是题目定义的延伸并没有额外的魔法。3.3 AI 辅助刷题的三个心得用 AI 辅助刷题这件事我在 895 上收获不小但也踩过一些无效提问的坑分享三个心得。第一先自己思考至少 10 分钟再问 AI。如果一上来就找答案这道题基本上就白刷了。我自己是先尝试了“哈希表 遍历找最大频率”的暴力解法确认超时之后才去问 AI这样我才能理解为什么需要group这个数据结构。第二先要思路再要代码最后自己默写。从 AI 拿到思路后我先把代码合上自己假装在面试在白板上写实现。写不出来再看 AI 给的参考代码然后继续默写。来回两三次之后这段代码就变成我自己的了。第三用测试用例验证而不是只跑 LeetCode 的示例。我上面手动推演的例子就是典型的“自定义用例”它能覆盖代码里最容易出错的maxFreq下降逻辑。如果你只在 LeetCode 上跑示例大概率一把过但面试官稍微改一下输入就可能翻车。4. 常见问题与排查技巧实录4.1 最容易踩的三个坑我必须承认代码第一版跑出来并不是直接 Accepted。我遇到的第一个问题是ArrayDeque不允许null元素但这个问题在这里不会出现因为我的输入没有 null。真正让我卡住的是group中同一个val被多次加入不同频率栈时pop 后group[maxFreq]变空但freq[val]还没减到 0 的情况。有一道非常经典的边界测试push(1) push(2) pop() // 返回 2maxFreq 从 1 降为 0这里因为我maxFreq维护得当pop 后group[1]还有元素 1所以不会降为 0。但如果我在 pop 里写成if (group.get(maxFreq).isEmpty()) maxFreq--;当group[1]为空时就会变成 0这时候再 pop 就会异常。所以第二个坑就是不要在maxFreq降到 0 之后继续调用 pop否则会越界。第三个坑是freq.put(val, freq.get(val) - 1)之后如果频率变成 0不要手动把freq[val]删除。虽然删掉也不影响后续逻辑但如果你在push时用getOrDefault(val,0)删掉跟不删本质一样。但如果你在别的地方有遍历freq.keySet()的逻辑删掉反而可能引起ConcurrentModificationException。所以为了安全起见我选择不删。4.2 正确性验证方法LeetCode 这类题很容易出现“示例过了但隐藏测试过不了”的情况。我的经验是准备一组自己的测试用例覆盖以下几类场景场景操作序列期望结果单元素多次 pushpush(1) x5, pop() x5每次返回 1最后为空多元素同频push(1), push(2), push(1), push(2), pop()第一次 pop 返回 2频率跳变push(1), push(2), push(1), push(2), push(1), pop()返回 1此时 2 的频率为 2pop 返回 2混合操作push, pop, push, push, pop, pop逐步核对 maxFreq 变化我每次写完这种栈类题目都会把这些用例跑一遍。尤其是第 3 个场景能有效地检查maxFreq下降后group[2]是否仍然存在且非空。另外我也喜欢用“双栈模拟法”做交叉验证用暴力法实现一个低效但正确的版本然后用随机操作序列对比两个版本的结果。我的做法是写了一个BruteFreqStackpop 时遍历freq找到最大频率然后从最早到最晚找出该频率的元素取最后一个。随机产生 1 万次操作对比两个栈的输出。这个方法虽然笨但能极快地暴露实现里的隐藏 bug。4.3 和主流题解的差异对比LeetCode 讨论区里大家比较常用的写法有两种一种是MapInteger, StackInteger group另一种是ArrayListStackInteger group。我最初用Map后来看到不少题解用List版本class FreqStack { MapInteger, Integer freq; ListStackInteger group; int maxFreq; public FreqStack() { freq new HashMap(); group new ArrayList(); maxFreq 0; } public void push(int val) { int f freq.getOrDefault(val, 0) 1; freq.put(val, f); if (group.size() f) group.add(new Stack()); group.get(f).push(val); maxFreq Math.max(maxFreq, f); } public int pop() { int val group.get(maxFreq).pop(); freq.put(val, freq.get(val) - 1); while (maxFreq 0 group.get(maxFreq).isEmpty()) maxFreq--; return val; } }这个写法和Map版本其实没本质区别只是用数组索引替代了哈希表的 key。两种写法都行但我个人更推荐Map版本因为它在内存上更稀疏不是每个频率都需要创建栈。如果你用List版本频率一旦很大比如 maxFreq 10^6你会创建 10^6 个栈对象哪怕大多数是空的内存开销也不小。另外一个细节有些题解在 pop 时用while循环把maxFreq降到“非空”而不是只减一次。理论上如果group[maxFreq]为空说明maxFreq应该减少但减少后的maxFreq - 1可能也是空吗在正确维护maxFreq的算法中这种情况是不会发生的。但如果你在某个环节出错了用while循环可以在一定程度上掩盖逻辑错误让你少 fail 几次。不过我觉得这种“掩盖式”的写法不太利于发现问题所以我自己还是喜欢严格的一次减一。5. 题目变形与扩展思路5.1 如果要求 pop 返回“最早插入的高频元素”把题目改一下如果同频率元素之间要求返回“最早进入该频率”的元素而不是最靠近栈顶的那该怎么办最简单的办法是把group[f]的“栈”改成“队列”也就是先进先出。每次 push 时从队尾进入pop 时从队头取出。这样一来同频元素就会按照“进入该频率的时间顺序”被弹出。这里需要注意ArrayDeque可以实现队列也可以实现栈。只看你调用的是push/pop还是offer/poll。如果你用LinkedList也同理。所以题目语义一变我们只需要更换容器的操作方式整体的双哈希表框架完全不用动。这也说明了为什么这个解法的本质是“频率分组 分组内顺序维护”。5.2 如果要求支持“返回频率前 K 高的元素”LeetCode 的另一种常见变形是不仅要返回频率最高的元素还需要支持查询频率前 K 高的元素。这个需求明显复杂不少因为单靠两个哈希表很难直接拿到“全局频率排序”。一种思路是维护一个平衡树key 是频率value 是该频率的元素集合再额外维护一个倒排索引。另一种思路是用 LFU 缓存的设计模式把“频率”作为链表节点每个频率下挂一个元素集合。这个思路在和 LeetCode 460 LFU Cache 的题解对比时很像。如果只是在面试里被问到我个人会先说明如果 K 很小可以维护一个 K 大小的堆每次 pop 后重建堆如果要求严格 O(1)就要引入更复杂的数据结构比如双向链表加哈希表。这样回答会让面试官觉得你对复杂度有清晰认识而不是硬背模板。5.3 类似题目延伸146、460、895 的共通之处LeetCode 146 LRU、460 LFU、895 最大频率栈这三道题放在一起看特别有意思。LRU 核心是“按访问时间排序”只要维护一个双向链表 哈希表即可。LFU 核心是“按访问频率排序同频再按时间排序”需要频率链表 每频下的双向链表。895 核心是“按全局频率排序同频按入栈时间排序”用两个哈希表就能搞定。它们的共同点是都需要在一个不断变化的序列里维护某种“优先级”并且要求增删改查在 O(1) 时间内完成。这种题本质上考的是“多个数据结构如何优雅地配合”而不是单个数据结构有多复杂。所以每刷完一道我都会把这几个题放在一起对照找它们的异同点。如果你把 895 吃透了再去看 460 LFU会发现核心思想有相似之处只是 LFU 还要额外处理“容量淘汰”和“最久未使用”这两个约束复杂度上了一个台阶。所以 895 是一个很好的跳板题。6. 实操总结与个人体会整个调试过程中我最大的感受是这道题不难但很考“拆解需求”的能力。题目只说“每次弹出频率最高且最靠近栈顶的元素”很多人第一眼会把它想成一个“动态 TOP 1 问题”于是拼命想在优先队列上做文章。但实际上只要你意识到“频率”是分档的每一档内部再按栈排序思路就豁然开朗。我自己写代码时有一个小习惯不管 AI 给了多好的思路我一定要先用纸笔把流程画一遍尤其把maxFreq升降的过程画清楚。因为pop过程中maxFreq的下降其实是一个很容易写的模棱两可的地方。画完流程再写代码基本一遍过。最后再分享一个实用小技巧如果面试时遇到这种“维护复杂优先级”的题目可以先大声说出你的数据结构选型。比如说“我打算用两个哈希表一个记录频率一个记录每个频率对应的栈维护一个当前最大频率变量”这样面试官马上能知道你的思路和你对复杂度的理解。即使还没写代码这一步已经能拿不少分了。如果你也在刷 LeetCode 的栈和哈希表专题895 绝对值得多花点时间研究。它不像很多 hard 题那样需要天马行空的算法直觉但它对“组合数据结构”的训练非常扎实。刷完之后再去看 341、394 这类栈相关的题目你会觉得从容很多。