最大频率栈

在这里插入图片描述

代码逻辑

这道题的关键在于：如何同时维护频率信息和时间顺序？

我们可以把栈想象成一个"蛋糕"，按频率分层：

第 1 层：存放所有出现过 1 次的元素
第 2 层：存放所有出现过 2 次的元素
第 3 层：存放所有出现过 3 次的元素
…

每当一个元素被 push 进来，它的频率加 1然后它会被添加到对应频率的那一层。

每当执行 pop 操作，从最高层（最大频率层）取出最后一个元素，如果该层变空，层数减 1。

1.数据结构设计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class FreqStack {
    // 当前最大频率
    private int topTimes;
    
    // 分层存储：频率 -> 该频率下的元素列表
    private HashMap<Integer, ArrayList<Integer>> cntValues= new HashMap<>();
    
    // 元素计数：元素值 -> 出现次数
    private HashMap<Integer, Integer> valueTimes== new HashMap<>();
}

2.push 操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public void push(int val) {
    // 更新该元素的频率
    valueTimes.put(val, valueTimes.getOrDefault(val, 0) + 1);
    int curTopTimes = valueTimes.get(val);
    
    // 将元素添加到对应频率层
    if (!cntValues.containsKey(curTopTimes)) {
        cntValues.put(curTopTimes, new ArrayList<>());
    }
    ArrayList<Integer> curTimeValues = cntValues.get(curTopTimes);
    curTimeValues.add(val);
    
    // 更新最大频率
    topTimes = Math.max(topTimes, curTopTimes);
}

3.pop 操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public int pop() {
    // 从最高层取出最后一个元素
    ArrayList<Integer> topTimeValues = cntValues.get(topTimes);
    int ans = topTimeValues.remove(topTimeValues.size() - 1);
    
    // 如果该层变空，删除该层并降低最高频率
    if (topTimeValues.size() == 0) {
        cntValues.remove(topTimes--);
    }
    
    // 更新元素的频率计数
    int times = valueTimes.get(ans);
    if (times == 1) {
        valueTimes.remove(ans);
    } else {
        valueTimes.put(ans, times - 1);
    }
    
    return ans;
}

完整代码

 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


class FreqStack{
        // 当前最大频率
        private int topTimes;

        // 分层存储：频率 -> 该频率下的元素列表
        private HashMap<Integer, ArrayList<Integer>> cntValues= new HashMap<>();

        // 元素计数：元素值 -> 出现次数
        private HashMap<Integer, Integer> valueTimes= new HashMap<>();

        public void push(int val) {
            // 更新该元素的频率
            valueTimes.put(val, valueTimes.getOrDefault(val, 0) + 1);
            int curTopTimes = valueTimes.get(val);

            // 将元素添加到对应频率层
            if (!cntValues.containsKey(curTopTimes)) {
                cntValues.put(curTopTimes, new ArrayList<>());
            }
            ArrayList<Integer> curTimeValues = cntValues.get(curTopTimes);
            curTimeValues.add(val);

            // 更新最大频率
            topTimes = Math.max(topTimes, curTopTimes);
        }

        public int pop() {
            // 从最高层取出最后一个元素
            ArrayList<Integer> topTimeValues = cntValues.get(topTimes);
            int ans = topTimeValues.remove(topTimeValues.size() - 1);

            // 如果该层变空，删除该层并降低最高频率
            if (topTimeValues.size() == 0) {
                cntValues.remove(topTimes--);
            }

            // 更新元素的频率计数
            int times = valueTimes.get(ans);
            if (times == 1) {
                valueTimes.remove(ans);
            } else {
                valueTimes.put(ans, times - 1);
            }

            return ans;
        }
    }

关注我，带你深度剖析更多经典算法题！ 🚀