LeetCode 895. 最大频率栈

约 6 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 字节 华为 百度 虾皮
标签
哈希表 栈 设计 有序集合

题目描述

✅ 895. 最大频率栈

image-20260929000609473

image-20260929000609474

题意分析

设计一种特殊栈：push 插入一个值，pop 删除并返回当前出现次数最多的值。如果多个值的当前频次相同，则删除其中最近入栈、仍未被删除的那一次出现。

一次弹出只移除一个元素，不是删除这个值的全部出现；频率也要随弹出减少。相同频率时比较的是剩余元素的入栈先后，而不是数值大小。题目保证调用 pop 时结构非空。

解法：频率分组栈

核心思路

[!blue]

需要同时知道最高频率和同频率元素的时间顺序。用 freq[val] 记录值的当前次数，maxFreq 记录当前最高次数，再用 groups[f] 保存一个栈：某次压入让值的频次从 f - 1 升到 f 时，就把这个值加入第 f 层的栈顶。

第 f 层记录的是“达到第 f 次出现”的入栈事件，并不是只存当前频率恰好等于 f 的值。一个目前出现了多次的值，会在多个低层各保留一条对应记录。这些记录维持了它每一次尚未弹出的出现所对应的先后关系，不需要在升频时从低层删除。

弹出时只看最高层 groups[maxFreq]。这一层的每条记录都对应当前频率达到最高值的元素，而它们按达到这一频率的入栈时间排在栈中；栈顶就是这些值里最近入栈的仍存活出现。因此直接弹出最高层栈顶，同时满足“频率最高”和“同频最近”两个条件。

弹出一个值后，它的频次降低一层，但不需要重新压入较低层：这个值之前达到较低频率时的记录还在原处，恰好代表剩余出现的原始时间。若重新压入，会伪造一次新的最近入栈事件，打乱它与其他同频值的先后关系。

如果最高层被弹空，说明再没有值维持这一频率，maxFreq 减一即可。下降不可能跳过更多层，因为刚被弹出的值只减少了一次：原最高频率大于一时，它还留下下一层记录；原最高频率为一时，最高层清空就表示整个结构为空，最大频率变为零。

解题步骤

  1. 构造空的频率表、频率分组表，令最高频率为零。
  2. push(val) 时，将该值频次加一，把值压入新频率对应的组栈，并更新 maxFreq。
  3. pop() 时，从最高频率组的栈顶取出一个值，将它的当前频次减一；降到零时删除该值的频率记录。
  4. 如果最高组已空，删除这个组并令 maxFreq--；否则保留该组剩余栈内容。
  5. 返回本次取出的值，不向低频组重新插入任何记录。

代码实现

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(q)$ 上界，q 为累计压入次数。每次压入只增加一条分层记录，每次弹出删除一条；逻辑记录数等于尚未弹出的元素数，容器容量可能保留此前的峰值。

关键点总结

[!green]

  • 当前频率决定去哪个组，组内栈顺序决定同频时先弹谁。
  • 分组保存每次升频的历史层级，低层记录会在高层弹出后重新成为有效候选。
  • 降频不重新入组，才能保留剩余出现的原始时间顺序。
  • 最高层清空时只需下降一层，由刚弹出值的剩余频率保证中间没有空缺。

易错点总结

[!yellow]

  • 把频率表当成累计入栈次数而不随弹出减少，会持续选错当前最高频元素。
  • 认为每个值只能出现在一个分组，并在升频时删除低层记录，会破坏之后降频所需的历史顺序。
  • 弹出后再压入低频组，会让旧出现看起来像刚刚入栈，错误抢占同频优先级。
  • 组内使用先进先出队列，会优先弹出同频最早而不是最近的元素。
  • 最高组清空后不降低 maxFreq，下一次弹出会读取空组。

相似题目

题目 难度 关联与区别
716. 最大栈 困难 原题优先弹最大值，本题优先弹最高频值；同优先级都取最近入栈者，需要兼顾两种顺序。
460. LFU 缓存 困难 LFU淘汰最低频且同频最旧，本题弹出最高频且同频最新，不能直接复用淘汰方向。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/94584971
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！