LeetCode 895. 最大频率栈

Categories:

题目描述
思路分析
1. 解法一：频次桶 + 栈（推荐）
相似题目

题目描述

✅ 895. 最大频率栈

思路分析

解法一：频次桶 + 栈（推荐）

核心思路：

freq[val] 记录元素出现次数。

group[f] 用栈保存所有出现次数为 f 的元素，保证同频次下后进先出。

maxFreq 记录当前最大频次，pop 直接从 group[maxFreq] 取。

复杂度分析：

时间复杂度：O(1)，所有操作均为均摊常数时间。

空间复杂度：O(n)，存储频次与分组栈。

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

    public void push(int val) {
        int f = freq.getOrDefault(val, 0) + 1;
        freq.put(val, f);

        group.computeIfAbsent(f, k -> new ArrayDeque<>()).push(val);
        if (f > maxFreq) {
            maxFreq = f;
        }
    }

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

        freq.put(val, freq.get(val) - 1);
        if (stack.isEmpty()) {
            maxFreq--;
        }

        return val;
    }
}

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

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

func (fs *FreqStack) Push(val int) {
    fs.freq[val]++
    f := fs.freq[val]

    fs.group[f] = append(fs.group[f], val)
    if f > fs.maxFreq {
        fs.maxFreq = f
    }
}

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

    fs.freq[val]--
    if len(fs.group[fs.maxFreq]) == 0 {
        fs.maxFreq--
    }

    return val
}

相似题目

题目	难度	考察点
155. 最小栈	简单	栈
347. 前 K 个高频元素	中等	哈希表、堆
380. O(1) 时间插入、删除和获取随机元素	中等	哈希表、数组
355. 设计推特	中等	哈希表、堆
895. 最大频率栈	困难	计数、栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/94584971