LeetCode 895. 最大频率栈

2025-09-10 HGNULB 约 6 分钟

文章信息 9 个分类 4 个标签

分类

题目描述

✅ 895. 最大频率栈

题意分析

题目要设计一个容器，支持两个操作：放入一个整数，以及取出「出现次数最多」的整数；当多个数的出现次数并列最多时，必须取出其中最后被放进来的那个。取出之后，这个数的出现次数相应减少一次。

两个约束叠在一起是本题的全部难点：主排序键是出现次数，次排序键是放入时刻，而且主排序键会随着每次取出而动态回退。也就是说，某个数今天是「冠军」，被取走一次后可能立刻退回到并列第二，还得和别的数按放入时刻重新比先后。

数据范围提示这是一道设计题：调用次数可达 $2 \times 10^4$ 量级，值域也不小，所以每次操作只能付出接近常数的代价，任何「每次取出都扫一遍所有出现过的值」的做法都在预算之外。

边界情形有三类：容器里只有一种值时反复取出；多个值出现次数完全相同，此时结果只由放入顺序决定；某个数被取到出现次数归零后又重新放入，它必须重新参与排序而不能残留旧的先后关系。题目保证 pop 只在非空时调用，所以不需要处理空容器。

解法：频率分组栈

核心思路

如果 pop 时再遍历所有值寻找最高频率，单次操作会退化为线性。更直接的做法是把信息在 push 时记好：freq[x] 记录值 x 的当前频率，group[f] 用栈记录“频率刚刚升到 f 的值”，maxFreq 记录当前最高频率。

当 x 的频率由 f - 1 升到 f 时，把 x 压入 group[f]。同一频率组内按压入时间排列，因此 group[maxFreq] 的栈顶同时满足两个条件：频率最高，并且在并列者中最近入栈。

不变量是：maxFreq 等于容器内的最高频率；每个 group[f] 的有效栈顶，是最近一次到达频率 f 且尚未被对应 pop 消耗的值。弹出最高频率组栈顶后，将该值频率减一；若该组变空，最高频率恰好下降一层。

该结构不需要时间戳和堆。栈的后进先出顺序已经表达了题目要求的“同频时最近者优先”。

解题步骤

push(val)：令 freq[val] 加一，得到新频率 f。

把 val 压入 group[f]，并更新 maxFreq。

pop()：从 group[maxFreq] 栈顶弹出答案。

将答案的当前频率减一；减到 0 时可删除 freq 中的键。

若最高频率组已空，删除该组并令 maxFreq--。

依次压入 5, 7, 5, 7, 4, 5 后，最高频率为 3，group[3] 栈顶是 5，第一次弹出 5；随后最高频率降为 2，group[2] 的栈顶是后到达频率 2 的 7，所以第二次弹出 7。

代码实现

import java.util.*;

class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();
    private final Map<Integer, Deque<Integer>> groups = new HashMap<>();
    private int maxFreq;

    public void push(int val) {
        int f = freq.getOrDefault(val, 0) + 1;
        freq.put(val, f);
        groups.computeIfAbsent(f, key -> new ArrayDeque<>()).push(val);
        maxFreq = Math.max(maxFreq, f);
    }

    public int pop() {
        Deque<Integer> stack = groups.get(maxFreq);
        int val = stack.pop();

        int f = freq.get(val) - 1;
        if (f == 0) {
            freq.remove(val);
        } else {
            freq.put(val, f);
        }

        if (stack.isEmpty()) {
            groups.remove(maxFreq);
            maxFreq--;
        }
        return val;
    }
}

type FreqStack struct {
    freq    map[int]int
    groups  map[int][]int
    maxFreq int
}

func Constructor() FreqStack {
    return FreqStack{
        freq:   make(map[int]int),
        groups: make(map[int][]int),
    }
}

func (this *FreqStack) Push(val int) {
    this.freq[val]++
    f := this.freq[val]
    this.groups[f] = append(this.groups[f], val)
    if f > this.maxFreq {
        this.maxFreq = f
    }
}

func (this *FreqStack) Pop() int {
    stack := this.groups[this.maxFreq]
    val := stack[len(stack)-1]
    stack = stack[:len(stack)-1]

    this.freq[val]--
    if this.freq[val] == 0 {
        delete(this.freq, val)
    }
    if len(stack) == 0 {
        delete(this.groups, this.maxFreq)
        this.maxFreq--
    } else {
        this.groups[this.maxFreq] = stack
    }
    return val
}

复杂度分析

时间复杂度：push 和 pop 的期望时间都是 $O(1)$，只进行常数次哈希表和栈操作。

空间复杂度：$O(n)$，其中 $n$ 是容器中的元素个数。每次 push 在分组栈中增加一条记录，每次 pop 恰好删除一条。

关键点总结

主排序键“频率”用分组表达，次排序键“最近”直接交给组内栈。

group[f] 记录的是达到频率 f 的时间顺序，而不是当前所有频率为 f 的去重集合。

maxFreq 使最高频率查询保持常数时间；最高组清空时只会下降一层。

这是“用空间记录历史层级，换取动态优先级常数操作”的典型设计题。

易错点总结

只维护 freq，在 pop 时扫描全部键，会把操作复杂度变成 $O(k)$。

group[f] 使用队列而不是栈，会在同频时弹出最早加入者，违反最近优先。

把一个值只放进其当前最高频组，会丢失降频后的历史顺序，pop 后无法正确回到下一层。

最高频组变空后忘记减少 maxFreq，下一次 pop 会访问空栈。

弹出后只改分组栈、不减少 freq[val]，后续压入该值时会进入错误的频率组。

并列规则比较的是最近一次 push 的顺序，不是值第一次出现的顺序。

相似题目

题目	难度	考察点
432. 全 O(1) 的数据结构	困难	同样按计数分组，但要求同时返回最大与最小计数键，需双向链表串联计数桶而非单变量跟踪
460. LFU 缓存	困难	次键从「最近放入」变为「最久未用」，且需要按容量淘汰，桶内要支持任意位置删除
347. 前 K 个高频元素	中等	静态一次性求前 $K$ 大频率，无需支持动态增删，也不涉及并列时的时间先后
155. 最小栈	中等	同为在栈上附加极值查询，但极值随出栈的回退靠辅助栈快照而非计数分层
380. O(1) 时间插入、删除和获取随机元素	中等	同样追求每操作常数时间，目标换成等概率随机取值，靠数组加下标表的尾部交换实现
451. 根据字符出现频率排序	中等	只需按频率整体排序输出，频率不会动态回退，并列时顺序任意