经典题解析：设计一个最大频率栈，push 和 pop 都要快

图 1：本文封面，点明题目与复杂度要求。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料，与任何公司的当前招聘无关。「最大频率栈」是数据结构设计题的代表：push 照常压栈，pop 弹出的不是最后压入的，而是当前出现次数最多的元素；次数并列时，弹出这些元素里最近压入的那个。要求 push 和 pop 都足够快。

想象面试现场，面试官写完需求补一句：「两个操作都要 O(1)。」这一句话就堵死了所有「先存下来再说」的朴素思路。

先看朴素思路为什么不及格。

直觉解法是用一个哈希表记每个元素的次数，pop 时全表扫描找最大频率。问题是每次 pop 都要 O(n) 扫描，n 是不同元素的个数。升级版是用最大堆按频率排序——但频率在 push 时不断变化，堆里元素的优先级失效要重建，维护成本同样不是 O(1)。两个思路共同的病根是：把「找最大频率」当成了每次弹出时的临时计算。

核心转念：把排序问题变成查表问题。

答案只需要三张「表」：freq 哈希表，记录每个元素当前出现了几次；group 哈希表，把同一频率的元素装进一个栈；maxFreq 变量，记住当前最高频率是多少。

push(x) 时：freq[x] 加一，把 x 压入新频率对应的那个栈，顺手更新 maxFreq。pop() 时：从 maxFreq 桶的栈顶弹元素——桶内是栈，天然保证「同频时后进先出」；freq[x] 减一；如果这个桶弹空了，maxFreq 降一档。每个动作都是哈希表查改加栈操作，push 和 pop 双双 O(1)。

走查一遍：依次 push 5、push 7、push 5 之后，freq 是 5→2、7→1；group 里频率 1 的桶是 [5, 7]，频率 2 的桶是 [5]；maxFreq=2。第一次 pop 从频率 2 的桶弹出 5，桶空，maxFreq 降为 1；第二次 pop 从频率 1 的桶顶弹出 7——注意不是 5，因为同频时栈顶（最近压入）优先。

写出可运行的代码。

下面这份实现附了两组走查，用 Node.js 22.15.0 直接运行（node freq-stack.js）即可：

'use strict';

// 最大频率栈：两张哈希表 + 一个变量
class FreqStack {
  constructor() {
    this.freq = new Map(); // 元素 -> 当前出现次数
    this.group = new Map(); // 频率 -> 该频率的元素栈（同频时栈顶是最近压入的）
    this.maxFreq = 0; // 当前最高频率
  }

  push(x) {
    const f = (this.freq.get(x) ?? 0) + 1;
    this.freq.set(x, f);
    if (!this.group.has(f)) this.group.set(f, []);
    this.group.get(f).push(x);
    if (f > this.maxFreq) this.maxFreq = f;
  }

  pop() {
    const stack = this.group.get(this.maxFreq);
    const x = stack.pop(); // 最高频的桶，弹栈顶：天然满足「同频时后进先出」
    this.freq.set(x, this.freq.get(x) - 1);
    if (stack.length === 0) {
      this.group.delete(this.maxFreq);
      this.maxFreq -= 1; // 该频率的桶弹空了，最高频率降一档
    }
    return x;
  }
}

// 走查一：mini 示例
const demo = new FreqStack();
for (const x of [5, 7, 5]) demo.push(x);
console.log('走查一 push(5,7,5) 后两次 pop：', demo.pop(), demo.pop());

// 走查二：经典示例，验证同频时后进先出
const stack = new FreqStack();
for (const x of [5, 7, 5, 7, 4, 5]) stack.push(x);
const popped = [stack.pop(), stack.pop(), stack.pop(), stack.pop()];
console.log('走查二 push(5,7,5,7,4,5) 后四次 pop：', popped.join(', '));

实测输出：

走查一 push(5,7,5) 后两次 pop： 5 7
走查二 push(5,7,5,7,4,5) 后四次 pop： 5, 7, 5, 4

走查二值得对一遍：5 出现 3 次最高频先出；之后 7 和 5 同为 2 次，7 更晚压入所以先出；再是 5，最后是 4。与「最高频优先、同频后进先出」完全吻合。

图 2：两张哈希表加一个变量，push 与 pop 双双 O(1)。

可能的追问。

「maxFreq 减一，新桶一定存在吗？」一定。弹空的桶里元素频率集体降了一档，至少刚弹出的那个元素落进了 maxFreq-1 的桶，所以降一档后桶必然非空。「空间复杂度多少？」O(n)，每个元素在每个频率桶里最多出现一次。「这思路还能用在哪？」按频率或优先级取元素的场合都是同构的——缓存淘汰、请求调度，「组合多个简单结构」比「找一个万能结构」更贴近工程实践。

易错点清单。

一，pop 时全表扫描找最大频率，复杂度直接出局。二，同频时弹错顺序——题面要求的是同频里「最近压入」的，桶内必须用栈而不是队列。三，桶弹空后忘记下调 maxFreq，下次 pop 拿到 undefined。四，只说思路不交代边界：空栈 pop、单元素反复 push，都要能答。

回到面试现场，建议的答题节奏：先复述需求里的两个约束（最高频、同频后进先出），主动否定扫描与堆的朴素方案并说明复杂度原因，再给出「按频率分桶 + 桶内栈」的结构，配一遍走查，最后补边界与追问。设计题的高分从来不在结构本身，而在你展示「为什么是它」的淘汰过程。

你在面试里遇到过「设计一个 XX 结构」的题吗？是先给答案还是先推翻朴素解？欢迎分享。