参考链接:
题目:最大频率栈。
备注:本题在头条的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;
}
}