LeetCode 895. 最大频率栈 题解，熟练掌握数据结构、集合的解法。

题目

1895. 最大频率栈

https://leetcode.cn/problems/maximum-frequency-stack/

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

实现 FreqStack 类:

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

思路

这道题与 LeetCode 146. LRU 缓存 双向链表题解 类似。

都是在基础数据结构之上，增加了应用层功能。

LRU中，我们使用了链表来维护一个队列：

  • 数据写入时：
    • 如果数据已存在，则删除队列已有元素，将元素插入到队头；
    • 如果数据不存在，则直接将元素插入到队头；
  • 数据读取时：
    • 数据不存在，不做任何操作；
    • 数据存在：
      • 返回找到的数据（可能是KV结构）；
      • 删除数据原位置，将数据插入到队头；

为了提高效率，我们使用了双向链表+map，方便定位数据、原地删除数据、头尾增删数据。言下之意，我们可以使用粗暴的解决方式，只是效率不高。

LRU中，在原始集合基础上，对数据访问（读、写）增加了前置元素到队头的逻辑。

而本题所求最大频率栈，则是在栈的基础上，对对数据访问（读、写）增加了更新频率的逻辑。

维护频率值+map

思路

按照上述分析，我们需要维护、更新：

  • 频率
    • 集合元素最大频率
    • 每个元素对应频率
  • 栈
    • 负责读写

复杂度分析

时间
  • push
    • 操作均为map/stack O(1)复杂度
  • pop
    • 操作均为map/stack O(1)复杂度
空间

使用了额外的map stack，空间占用O(n)。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public class FreqStack {

    /**
     * 值 ——》频率
     */
    Map<Integer, Integer> val2Freq;
    /**
     * 频率--》栈结构
     */
    Map<Integer, Deque<Integer>> freq2Stack;
    /**
     * 当前最大频率
     */
    int maxFreq;

    public FreqStack() {
        val2Freq = new HashMap<>();
        freq2Stack = new HashMap<>();
        maxFreq = 0;
    }

    void push(int val) {
        // val对应频率+1
        Integer freq = val2Freq.getOrDefault(val, 0) + 1;
        // 更新val频率
        val2Freq.put(val, freq);
        freq2Stack.putIfAbsent(freq, new LinkedList<>());
        // val入栈新频率stack
        freq2Stack.get(freq).offerLast(val);
        // 当前数据频率最大，更新maxFreq
        maxFreq = Math.max(maxFreq, freq);
    }

    int pop() {
        // 根据maxFreq获取栈
        Deque<Integer> stack = freq2Stack.get(maxFreq);
        if (stack.isEmpty()) {
            return -1;
        }
        Integer val = stack.pollLast();
        // 更新val对应频率，频率-1
        val2Freq.put(val, val2Freq.get(val) - 1);
        // 栈空，表示当前频率下没元素了，最大频率-1
        if (stack.isEmpty()) {
            maxFreq--;
        }
        return val;
    }
}