题目链接
思路
很容易想到使用 map：valToFreq 来记录每个值出现的频率，这是没问题的，但关键是如何通过频率寻找到应该返回的数。
这时候我想到再加一个 map：freqToVal 来记录每个频率中出现的数字，为了符合题目返回最接近栈顶的元素的要求，freqToVal 的键值对类型选择 <Integer, Deque<Integer>>，这样如果两个元素是同频率的，就会返回最接近栈顶的元素。
代码
class FreqStack {
// 当前 FreqStack 中的最大频率值
int maxFreq;
// 记录 FreqStack 中每个元素出现的频率
TreeMap<Integer, Integer> valToFreq;
// 记录每个频率对应的元素值
TreeMap<Integer, Deque<Integer>> freqToVal;
public FreqStack() {
this.maxFreq = 0;
this.valToFreq = new TreeMap<>();
this.freqToVal = new TreeMap<>();
}
public void push(int val) {
valToFreq.put(val, valToFreq.getOrDefault(val, 0) + 1);
int freq = valToFreq.get(val);
maxFreq = Math.max(maxFreq, freq);
// 第一次出现这个频率
if(!freqToVal.containsKey(freq)){
freqToVal.put(freq, new ArrayDeque<>());
}
freqToVal.get(freq).push(val);
}
public int pop() {
Deque<Integer> stack = freqToVal.get(maxFreq);
int result = stack.pop();
valToFreq.put(result, valToFreq.getOrDefault(result, 0) - 1);
// 如果当前频率没有元素了,就需要更新最大频率
while(
maxFreq > 0 &&
(
!freqToVal.containsKey(maxFreq) ||
freqToVal.getOrDefault(maxFreq, new ArrayDeque<>()).isEmpty()
)
){
maxFreq--;
}
return result;
}
}