Closed congr closed 5 years ago
class FreqStack {
class Item {
int index, value, freq;
Item(int value, int index, int freq) {
this.value = value;
this.index = index;
this.freq = freq;
}
}
int index;
PriorityQueue<Item> pq;
Map<Integer, Integer> map;
public FreqStack() {
map = new HashMap();
pq = new PriorityQueue<>((a,b) -> (a.freq == b.freq) ?
b.index - a.index: b.freq - a.freq);
index = 0;
}
public void push(int x) {
map.merge(x, 1, Integer::sum);
pq.add(new Item(x, index++, map.get(x)));
}
public int pop() {
int value = pq.remove().value;
map.merge(value, -1, Integer::sum);
return value;
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(x);
* int param_2 = obj.pop();
*/
https://leetcode.com/problems/maximum-frequency-stack/