LeetCode: 895. 最大频率栈 FreqStack

382 阅读2分钟

参考链接:

leetcode-cn.com/articles/ma…

题目:最大频率栈。

备注:本题在头条的Android面试中出现过。

youtube找到一个对本题的视频讲解:

花花酱 LeetCode 895. Maximum Frequency Stack

输入:
["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]
解释:
执行六次 .push 操作后,栈自底向上为 [5,7,5,7,4,5]。然后:

pop() -> 返回 5,因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7,因为 5 和 7 都是频率最高的,但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

思路分析

本题明显是一道组合型数据结构题,核心是建立出所需数据结构模型。

Step1:

题目中提到最大频率,因此需要元素 maxFreq。

Step2

题目中可以看出,每个元素都需要有查出其出现频率的功能,因此需要对元素和频率做一个key:Value 键值对查询数据结构:Map<Integer, Integer>,即 “元素:频率” 键值对

难点

Step3

每次弹出频率最大,且最近的元素。由于需要最大频率对应的值可能有多个,而且这些值还有先后顺序。

那么首先需要一个 Map 来做 key(频率):value(元素组合)的键值对。

这样我们就可以根据最大频率来快速查询(O(1)时间复杂度)该频率下的所有元素集合。

Step4:

接着再根据得到的元素集合,获取最近添加的元素,符合 “后进先出” 原则,因此此处确定元素集合的数据结构是栈 Stack<Integer>

最终确定的数据结构是:Map<Integer, Stack<Integer>>

至此,我们确定了所需的数据结构。

题解代码:

class FreqStack {

    //元素1、最大频率值
    int maxFreq; 
    
    //元素2、存放每个不同元素出现的频率,用于push和pop的查询依据
    Map<Integer, Integer> freqMap = null; 
    
    //元素3、由于需要最大频率对应的值可能有多个,而且这些值还有先后顺序。
    
    //因此我们需要的数据结构需要具备两个功能点:
    //1、根据最大频率值查询到元素集合:对应 Map;2、元素具备先后顺序,后进先出,对应 Stack。
    
    //据此,可以反推出所需数据结构模型:Map + Stack = Map<Integer, Stack<Integer>>。
    //其中的 key 对应最大频率值,Stack 对应相同频率的元素组合。
    
    Map<Integer, Stack<Integer>> groupStackMap = null;

    public FreqStack() {
        maxFreq = 0;
        freqMap = new HashMap<>();
        groupStackMap = new HashMap<>();
    }
    
    public void push(int x) {
        int curNewFreq = freqMap.getOrDefault(x, 0) + 1;
        if(curNewFreq > maxFreq) {
            maxFreq = curNewFreq;
        }
        freqMap.put(x, curNewFreq);
        Stack<Integer> stack = groupStackMap.get(curNewFreq);
        if(stack == null) {
            stack = new Stack<>();
        }
        stack.push(x);
        groupStackMap.put(curNewFreq, stack);
    }
    
    public int pop() {
        int x = groupStackMap.get(maxFreq).pop();
        if(groupStackMap.get(maxFreq).size() == 0) {
            maxFreq --;
        }
        freqMap.put(x, freqMap.get(x) - 1);
        return x;
    }
}

附 LeetCode 运行结果: