895. 最大频率栈

题目描述

设计一个类似栈的数据结构，将元素推入栈，并从栈中弹出 出现频率最高 的元素。

实现 FreqStack 类：

FreqStack() 构造一个空的最大频率栈。
void push(int val) 将整数 val 压入栈顶。
int pop() 删除并返回栈中出现频率最高的元素。
- 如果出现频率最高的元素不止一个，则返回 最接近栈顶 的那个元素。

示例

text

输入：
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]

输出：
[null, null, null, null, null, null, null, 5, 7, 5, 4]

解释

text

FreqStack freqStack = new 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 出现频率最高
freqStack.pop();   // 返回 7 ，因为 5 和 7 频率相同，但 7 更接近栈顶
freqStack.pop();   // 返回 5
freqStack.pop();   // 返回 4

约束

0 <= val <= 10^9
在调用 pop() 前，栈中至少有一个元素
push 和 pop 操作总数最多为 2 * 10^4

核心思路

这题看起来像“栈”，但真正决定 pop() 返回谁的，不只是“谁在栈顶”，而是两层规则：

先看频率谁最高
如果频率相同，再看谁更靠近栈顶

所以这题本质上要同时维护两种信息：

每个数字当前出现了多少次
每个频率层里，元素的“入栈先后顺序”

这题至少有两种常见做法：

解法一：频率表 + 按频率分组的栈（推荐）
解法二：优先队列 / 大根堆模拟

先理解：为什么普通栈不够？

假设入栈顺序是：

text

5, 7, 5, 7, 4, 5

此时频率：

5 出现 3 次
7 出现 2 次
4 出现 1 次

第一次 pop() 应该返回 5，因为频率最高。

这没问题。

但再弹一次后，频率变成：

5 出现 2 次
7 出现 2 次
4 出现 1 次

这时不能随便返回一个频率为 2 的数，而要返回：

更靠近栈顶的那个

也就是 7。

所以题目不是单纯比较频率，还带有“时间顺序”的要求。

解法一：频率表 + 按频率分组的栈

这是本题最经典、最推荐掌握的做法。

思路拆解

我们维护三个东西：

freq[val]：数字 val 当前频率是多少
group[f]：一个栈，存“当前频率达到 f 时入组”的元素
maxFreq：当前全局最大频率

这里最巧妙的地方在 group[f]：

当某个值的频率变成 f 时
就把它压入 group[f]

这样一来：

group[maxFreq] 的栈顶
就一定是“当前最大频率里，最近入栈的那个元素”

这正好完全符合题目要求。

为什么这个方法是对的？

假设当前某个元素 x 的频率从 2 变成了 3。

我们就把它压入 group[3]。

这样：

所有频率为 3 的元素，都会按“达到频率 3 的时间顺序”存在 group[3] 中
后达到频率 3 的元素，会在栈顶

因此，当我们要弹出“频率最高、且最靠近栈顶”的元素时：

直接从 group[maxFreq] 弹出即可

这就是这题的核心技巧。

一步一步写出算法

第一步：定义数据结构

class FreqStack {
    private freq: Map<number, number>
    private group: Map<number, number[]>
    private maxFreq: number

    constructor() {
        this.freq = new Map()
        this.group = new Map()
        this.maxFreq = 0
    }
}

第二步：实现 `push(val)`

先让该值频率加一：

const count = (this.freq.get(val) ?? 0) + 1
this.freq.set(val, count)

然后把它加入对应频率组：

if (!this.group.has(count)) {
    this.group.set(count, [])
}
this.group.get(count)!.push(val)

最后更新最大频率：

this.maxFreq = Math.max(this.maxFreq, count)

第三步：实现 `pop()`

从最大频率组的栈顶弹出：

const values = this.group.get(this.maxFreq)!
const val = values.pop()!

然后把这个值的频率减一：

this.freq.set(val, this.freq.get(val)! - 1)

如果当前最大频率组已经空了，说明最大频率应该下降：

if (values.length === 0) {
    this.group.delete(this.maxFreq)
    this.maxFreq--
}

最后返回这个值。

代码实现（TypeScript）

class FreqStack {
    private freq: Map<number, number>
    private group: Map<number, number[]>
    private maxFreq: number

    constructor() {
        this.freq = new Map()
        this.group = new Map()
        this.maxFreq = 0
    }

    push(val: number): void {
        const count = (this.freq.get(val) ?? 0) + 1
        this.freq.set(val, count)

        if (!this.group.has(count)) {
            this.group.set(count, [])
        }
        this.group.get(count)!.push(val)

        this.maxFreq = Math.max(this.maxFreq, count)
    }

    pop(): number {
        const values = this.group.get(this.maxFreq)!
        const val = values.pop()!

        this.freq.set(val, this.freq.get(val)! - 1)

        if (values.length === 0) {
            this.group.delete(this.maxFreq)
            this.maxFreq--
        }

        return val
    }
}

复杂度分析

push 时间复杂度：O(1)
pop 时间复杂度：O(1)
空间复杂度：O(n)

这里的 n 是操作过程中压入过的元素总数。

这一解法的优缺点

优点：

时间复杂度最优
思路非常巧妙
是这题标准解法

缺点：

第一次想到 group[freq] 这种设计不太直观

解法二：优先队列 / 大根堆模拟

这个做法更贴近“按规则选最大值”的直觉。

思路拆解

每次 push(val) 时，我们记录一个三元组：

当前频率 freq
当前入栈时间 time
当前值 val

然后放进一个大根堆里。

堆的优先级规则是：

频率大的优先
如果频率相同，时间晚的优先

这样堆顶元素就正好是：

频率最高
且最近入栈

的元素。

不过这里有一个细节：

某个值的频率会变化
堆里会残留一些旧状态

所以我们需要结合 freq 表，在 pop() 时判断堆顶是不是当前有效状态；如果不是，就继续弹掉旧状态。

一步一步写出算法

第一步：定义堆元素

每次插入一个元素，存：

[count, time, val]

第二步：`push(val)`

更新 freq[val]
时间戳加一
把 [freq[val], time, val] 放进大根堆

第三步：`pop()`

不断查看堆顶：

如果堆顶记录的频率，和当前 freq[val] 一致
说明这是有效状态，直接返回
否则说明这是旧记录，丢掉继续看下一个

这样就能实现“惰性删除”。

代码实现（TypeScript）

class MaxHeap {
    private data: [number, number, number][] = []

    private greater(a: [number, number, number], b: [number, number, number]): boolean {
        if (a[0] !== b[0]) {
            return a[0] > b[0]
        }
        return a[1] > b[1]
    }

    push(value: [number, number, number]): void {
        this.data.push(value)
        this.bubbleUp(this.data.length - 1)
    }

    pop(): [number, number, number] | undefined {
        if (this.data.length === 0) {
            return undefined
        }

        const top = this.data[0]
        const last = this.data.pop()!
        if (this.data.length > 0) {
            this.data[0] = last
            this.bubbleDown(0)
        }
        return top
    }

    peek(): [number, number, number] | undefined {
        return this.data[0]
    }

    get size(): number {
        return this.data.length
    }

    private bubbleUp(index: number): void {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2)
            if (this.greater(this.data[parent], this.data[index])) {
                break
            }
            ;[this.data[parent], this.data[index]] = [this.data[index], this.data[parent]]
            index = parent
        }
    }

    private bubbleDown(index: number): void {
        const n = this.data.length
        while (true) {
            let largest = index
            const left = index * 2 + 1
            const right = index * 2 + 2

            if (left < n && this.greater(this.data[left], this.data[largest])) {
                largest = left
            }
            if (right < n && this.greater(this.data[right], this.data[largest])) {
                largest = right
            }
            if (largest === index) {
                break
            }
            ;[this.data[largest], this.data[index]] = [this.data[index], this.data[largest]]
            index = largest
        }
    }
}

class FreqStack {
    private freq: Map<number, number>
    private heap: MaxHeap
    private time: number

    constructor() {
        this.freq = new Map()
        this.heap = new MaxHeap()
        this.time = 0
    }

    push(val: number): void {
        const count = (this.freq.get(val) ?? 0) + 1
        this.freq.set(val, count)
        this.time++
        this.heap.push([count, this.time, val])
    }

    pop(): number {
        while (this.heap.size > 0) {
            const [count, _, val] = this.heap.pop()!
            if ((this.freq.get(val) ?? 0) === count) {
                this.freq.set(val, count - 1)
                return val
            }
        }

        return -1
    }
}

复杂度分析

push 时间复杂度：O(log n)
pop 平均 / 均摊复杂度：O(log n)
空间复杂度：O(n)

这一解法的优缺点

优点：

更符合“按优先级选最大”的直觉
对“频率 + 时间”这种排序规则理解更直接

缺点：

不如第一种做法高效
需要自己维护堆和惰性删除
代码量更大

两种解法对比

解法	`push`	`pop`	空间复杂度	特点
频率表 + 分组栈	`O(1)`	`O(1)`	`O(n)`	标准解法，最推荐
大根堆模拟	`O(log n)`	`O(log n)`	`O(n)`	更直观，但更复杂

如果你是第一次做这题，建议直接掌握第一种方法。

手动模拟一遍标准解法

入栈顺序：

text

5, 7, 5, 7, 4, 5

前几次 `push`

`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]

`push(5)`

freq[5] = 3
group[3] = [5]
maxFreq = 3

第一次 `pop()`

从 group[3] 弹出栈顶：

text

因为频率最高就是 3。

第二次 `pop()`

现在：

5 频率变成 2
7 频率也是 2

看 group[2]：

text

[5, 7]

栈顶是 7，说明在“频率为 2 的元素里”，7 更接近栈顶。

所以第二次弹出：

text

这正好符合题意。

面试时最容易错的点

1. 不是简单地弹出“出现次数最多”的值

如果频率相同，还要看：

谁更接近栈顶

所以不能只维护一个频率表。

2. `group[freq]` 里存的是“达到这个频率时的顺序”

这是第一种解法最关键的理解点。

一旦想明白这一点，整题就顺了。

3. `maxFreq` 在 `pop()` 后可能下降

如果：

group[maxFreq] 弹完变空

就要：

maxFreq--

4. 堆解法要处理旧状态

因为频率会变化，所以堆里会保留一些过期记录。

这时必须做惰性删除，不能直接信任堆顶一定有效。

一句话总结

这题的本质是：

既要按“频率”选最大，又要在频率相同时按“最近入栈”选最大。

想写标准最优解：用 频率表 + 分组栈
想从优先级角度理解：用 大根堆模拟

895. 最大频率栈

题目描述

示例

解释

约束

核心思路

先理解：为什么普通栈不够？

解法一：频率表 + 按频率分组的栈

思路拆解

为什么这个方法是对的？

一步一步写出算法

第一步：定义数据结构

第二步：实现 push(val)

第三步：实现 pop()

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：优先队列 / 大根堆模拟

思路拆解

一步一步写出算法

第一步：定义堆元素

第二步：push(val)

第三步：pop()

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍标准解法

前几次 push

push(5)

push(7)

push(5)

push(7)

push(4)

push(5)

第一次 pop()

第二次 pop()

面试时最容易错的点

1. 不是简单地弹出“出现次数最多”的值

2. group[freq] 里存的是“达到这个频率时的顺序”

3. maxFreq 在 pop() 后可能下降

4. 堆解法要处理旧状态

一句话总结

推荐你最后记住的标准写法

第二步：实现 `push(val)`

第三步：实现 `pop()`

第二步：`push(val)`

第三步：`pop()`

前几次 `push`

`push(5)`

`push(7)`

`push(5)`

`push(7)`

`push(4)`

`push(5)`

第一次 `pop()`

第二次 `pop()`

2. `group[freq]` 里存的是“达到这个频率时的顺序”

3. `maxFreq` 在 `pop()` 后可能下降