05 August 2008
无非是选择一个合适的数据结构罢了。两个需求：
1
2
按频率出栈，需要记录最高频率。
相同频率的元素需要有时序。
确定了数据结构，接下来的push()和pop()方法实现时，只要考虑依次操作每个数据结构和维护最高频率maxFreq就不会有问题。使用HashMap结合LinkedList，插入、删除数据的时间复杂度都可以达到 O(1)。
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
class FreqStack {
HashMap<Integer, Integer> KF;
HashMap<Integer, LinkedList<Integer>> FK;
int maxFreq;
public FreqStack() {
KF = new HashMap<Integer, Integer>();
FK = new HashMap<Integer, LinkedList<Integer>>();
maxFreq = 0;
}
public void push(int val) {
int newFreq = KF.getOrDefault(val, 0) + 1;
KF.put(val, newFreq);
if(maxFreq < newFreq){
maxFreq++;
}
FK.putIfAbsent(newFreq, new LinkedList<Integer>());
FK.get(newFreq).push(val);
}
public int pop() {
int res = FK.get(maxFreq).pop();
if(FK.get(maxFreq).isEmpty()){
FK.remove(maxFreq);
maxFreq--;
}
KF.put(res, KF.get(res) - 1);
return res;
}
}