895. 最大频率栈
题目描述
设计一个类似栈的类 FreqStack，每次弹出的是当前出现次数最多的元素。
FreqStack()：创建一个空栈。
push(val)：把整数 val 放到栈顶，不返回值。
pop()：在栈中当前所有元素里，找出出现次数最多的值，移除并返回它。若有多个值出现次数并列最多，则在这些值中选取离栈顶最近的那一个元素移除并返回。
示例 1
输入：操作 = ["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]
解释：依次弹出：5 出现 3 次最多；5 和 7 都 2 次，7 更靠顶；5 剩 2 次最多；三者各 1 次，4 最靠顶。
数据范围
0 <= val <= 10^9push和pop的总调用次数不超过2 * 10^4。- 保证调用
pop时栈非空。
解题思路：哈希表 + 按频率分组的栈
用 freq 记录每个值当前的出现次数，用 group[f] 保存“第 f 次出现”的那些压入动作组成的小栈，再记录最高频率 maxf。push 时把值的频率加 1 得到 f，压入 group[f]；pop 时从 group[maxf] 弹出栈顶，它就是频率最高中最近的那个，把它的频率减 1，如果 group[maxf] 空了就 maxf -= 1。一个出现 3 次的值同时在 group[1]、group[2]、group[3] 里，所以频率降低后不需要搬动它。
为什么正确
group[1..maxf] 都非空，且值 v 恰好出现在 group[1..freq[v]] 中各一次；每个 group 内部按压入时间排列。
复杂度分析
push 和 pop 均为 O(1)；空间 O(n)。
易错点
很多人想用堆按 (频率, 时间) 排序，但弹出后另一份同值的频率变了，堆里的旧记录会失效。按频率分栈的关键是：不要把值从低频栈移到高频栈，而是每一层都保留一份。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class FreqStack:
def __init__(self):
self.freq = {}
self.group = {}
self.maxf = 0
def push(self, val: int) -> None:
f = self.freq.get(val, 0) + 1
self.freq[val] = f
if f > self.maxf:
self.maxf = f
if f not in self.group:
self.group[f] = []
self.group[f].append(val)
def pop(self) -> int:
val = self.group[self.maxf].pop()
self.freq[val] -= 1
if not self.group[self.maxf]:
self.maxf -= 1
return valclass FreqStack {
private Map<Integer, Integer> freq;
private Map<Integer, Deque<Integer>> group;
private int maxf;
public FreqStack() {
freq = new HashMap<>();
group = new HashMap<>();
maxf = 0;
}
public void push(int val) {
int f = freq.getOrDefault(val, 0) + 1;
freq.put(val, f);
if (f > maxf) {
maxf = f;
}
if (!group.containsKey(f)) {
group.put(f, new ArrayDeque<>());
}
group.get(f).push(val);
}
public int pop() {
int val = group.get(maxf).pop();
freq.put(val, freq.get(val) - 1);
if (group.get(maxf).isEmpty()) {
maxf--;
}
return val;
}
}class FreqStack {
public:
unordered_map<int, int> freq;
unordered_map<int, vector<int>> group;
int maxf;
FreqStack() {
freq.clear();
group.clear();
maxf = 0;
}
void push(int val) {
int f = freq[val] + 1;
freq[val] = f;
if (f > maxf) {
maxf = f;
}
group[f].push_back(val);
}
int pop() {
int val = group[maxf].back();
group[maxf].pop_back();
freq[val]--;
if (group[maxf].empty()) {
maxf--;
}
return val;
}
};type FreqStack struct {
freq map[int]int
group map[int][]int
maxf int
}
func Constructor() FreqStack {
freq := map[int]int{}
group := map[int][]int{}
return FreqStack{freq: freq, group: group, maxf: 0}
}
func (this *FreqStack) Push(val int) {
f := this.freq[val] + 1
this.freq[val] = f
if f > this.maxf {
this.maxf = f
}
this.group[f] = append(this.group[f], val)
}
func (this *FreqStack) Pop() int {
g := this.group[this.maxf]
val := g[len(g)-1]
this.group[this.maxf] = g[:len(g)-1]
this.freq[val]--
if len(this.group[this.maxf]) == 0 {
this.maxf--
}
return val
}class FreqStack {
constructor() {
this.freq = new Map();
this.group = new Map();
this.maxf = 0;
}
push(val) {
const f = (this.freq.get(val) || 0) + 1;
this.freq.set(val, f);
if (f > this.maxf) {
this.maxf = f;
}
if (!this.group.has(f)) {
this.group.set(f, []);
}
this.group.get(f).push(val);
}
pop() {
const val = this.group.get(this.maxf).pop();
this.freq.set(val, this.freq.get(val) - 1);
if (this.group.get(this.maxf).length === 0) {
this.maxf--;
}
return val;
}
}class FreqStack {
freq: Map<number, number>;
group: Map<number, number[]>;
maxf: number;
constructor() {
this.freq = new Map();
this.group = new Map();
this.maxf = 0;
}
push(val: number): void {
const f = (this.freq.get(val) || 0) + 1;
this.freq.set(val, f);
if (f > this.maxf) {
this.maxf = f;
}
if (!this.group.has(f)) {
this.group.set(f, []);
}
this.group.get(f)!.push(val);
}
pop(): number {
const val = this.group.get(this.maxf)!.pop()!;
this.freq.set(val, this.freq.get(val)! - 1);
if (this.group.get(this.maxf)!.length === 0) {
this.maxf--;
}
return val;
}
}其他解法
优先队列把排序规则交给堆来维护，是通用做法；分组栈利用频率只会加减 1 且最大频率连续变化的特点，把两个操作都做到 O(1)。
解法 2：优先队列（按频率、时间戳排序） 时间 push / pop 均 O(log n)，空间 O(n)
用哈希表记录每个值当前的频率，再维护一个存放三元组 (频率, 时间戳, 值) 的大根堆。push 时频率加 1，把 (新频率, 递增的时间戳, val) 压入堆；pop 时取出堆顶：频率最大的优先，频率相同时时间戳大（离栈顶最近）的优先，再把该值的频率减 1。同一个值的每次入栈都对应堆里的一个独立元素，所以堆中不会有过期数据。
把“先比频率、再比先后”的规则直接写成比较器，很容易想到也容易写对。代价是每次操作多一个 log n，而且没有利用“频率每次只变化 1”这一特点。
class FreqStack:
def __init__(self):
self.freq = {}
self.heap = []
self.time = 0
def push(self, val: int) -> None:
f = self.freq.get(val, 0) + 1
self.freq[val] = f
self.time += 1
heapq.heappush(self.heap, (-f, -self.time, val))
def pop(self) -> int:
val = heapq.heappop(self.heap)[2]
self.freq[val] -= 1
return valclass FreqStack {
private Map<Integer, Integer> freq;
private PriorityQueue<int[]> pq;
private int time;
public FreqStack() {
freq = new HashMap<>();
pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
time = 0;
}
public void push(int val) {
int f = freq.getOrDefault(val, 0) + 1;
freq.put(val, f);
pq.offer(new int[]{f, ++time, val});
}
public int pop() {
int val = pq.poll()[2];
freq.put(val, freq.get(val) - 1);
return val;
}
}class FreqStack {
public:
unordered_map<int, int> freq;
priority_queue<tuple<int, int, int>> pq;
int time;
FreqStack() {
time = 0;
}
void push(int val) {
int f = ++freq[val];
pq.push({f, ++time, val});
}
int pop() {
int val = get<2>(pq.top());
pq.pop();
freq[val]--;
return val;
}
};type freqHeap [][3]int
func (h freqHeap) Len() int { return len(h) }
func (h freqHeap) Less(i, j int) bool {
if h[i][0] != h[j][0] {
return h[i][0] > h[j][0]
}
return h[i][1] > h[j][1]
}
func (h freqHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *freqHeap) Push(x interface{}) { *h = append(*h, x.([3]int)) }
func (h *freqHeap) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
type FreqStack struct {
freq map[int]int
h *freqHeap
time int
}
func Constructor() FreqStack {
return FreqStack{freq: map[int]int{}, h: &freqHeap{}, time: 0}
}
func (this *FreqStack) Push(val int) {
this.freq[val]++
this.time++
heap.Push(this.h, [3]int{this.freq[val], this.time, val})
}
func (this *FreqStack) Pop() int {
val := heap.Pop(this.h).([3]int)[2]
this.freq[val]--
return val
}class FreqStack {
constructor() {
this.freq = new Map();
this.heap = [];
this.time = 0;
}
less(a, b) {
return a[0] !== b[0] ? a[0] > b[0] : a[1] > b[1];
}
push(val) {
const f = (this.freq.get(val) || 0) + 1;
this.freq.set(val, f);
const h = this.heap;
h.push([f, ++this.time, val]);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(h[i], h[p])) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
}
pop() {
const h = this.heap;
const top = h[0], last = h.pop();
if (h.length > 0) {
h[0] = last;
let i = 0;
while (true) {
let s = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < h.length && this.less(h[l], h[s])) s = l;
if (r < h.length && this.less(h[r], h[s])) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]];
i = s;
}
}
const val = top[2];
this.freq.set(val, this.freq.get(val) - 1);
return val;
}
}class FreqStack {
freq: Map<number, number>;
heap: number[][];
time: number;
constructor() {
this.freq = new Map();
this.heap = [];
this.time = 0;
}
less(a: number[], b: number[]): boolean {
return a[0] !== b[0] ? a[0] > b[0] : a[1] > b[1];
}
push(val: number): void {
const f = (this.freq.get(val) || 0) + 1;
this.freq.set(val, f);
const h = this.heap;
h.push([f, ++this.time, val]);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(h[i], h[p])) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
}
pop(): number {
const h = this.heap;
const top = h[0], last = h.pop()!;
if (h.length > 0) {
h[0] = last;
let i = 0;
while (true) {
let s = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < h.length && this.less(h[l], h[s])) s = l;
if (r < h.length && this.less(h[r], h[s])) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]];
i = s;
}
}
const val = top[2];
this.freq.set(val, this.freq.get(val)! - 1);
return val;
}
}