设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:
FreqStack()构造一个空的堆栈。void push(int val)将一个整数val压入栈顶。int pop()删除并返回堆栈中出现频率最高的元素。- 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
示例 1：
输入： ["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] 解释： FreqStack = new FreqStack(); freqStack.push (5);//堆栈为 [5] freqStack.push (7);//堆栈是 [5,7] freqStack.push (5);//堆栈是 [5,7,5] freqStack.push (7);//堆栈是 [5,7,5,7] freqStack.push (4);//堆栈是 [5,7,5,7,4] freqStack.push (5);//堆栈是 [5,7,5,7,4,5] freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。 freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。 freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。 freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。
提示：
0 <= val <= 109push和pop的操作数不大于2 * 104。- 输入保证在调用
pop之前堆栈中至少有一个元素。
方法一：哈希表 + 优先队列（大根堆）
根据题目描述，我们需要设计一个支持弹出“出现频率最高”的元素的数据结构。如果存在多个元素出现频率相同，那么弹出最接近栈顶的元素。
我们可以使用哈希表
执行压栈操作时，我们先将当前时间戳加一，即
执行弹栈操作时，我们直接从优先队列
方法二：双哈希表
在方法一中，为了能弹出符合要求的元素，我们维护了一个优先队列，每次都需要对优先队列进行操作，时间复杂度为
实际上，我们可以用一个变量
执行压栈操作时，我们将元素的频率加一，即
执行弹栈操作时，我们从哈希表
class FreqStack:
def __init__(self):
self.cnt = defaultdict(int)
self.q = []
self.ts = 0
def push(self, val: int) -> None:
self.ts += 1
self.cnt[val] += 1
heappush(self.q, (-self.cnt[val], -self.ts, val))
def pop(self) -> int:
val = heappop(self.q)[2]
self.cnt[val] -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()class FreqStack:
def __init__(self):
self.cnt = defaultdict(int)
self.d = defaultdict(list)
self.mx = 0
def push(self, val: int) -> None:
self.cnt[val] += 1
self.d[self.cnt[val]].append(val)
self.mx = max(self.mx, self.cnt[val])
def pop(self) -> int:
val = self.d[self.mx].pop()
self.cnt[val] -= 1
if not self.d[self.mx]:
self.mx -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()class FreqStack {
private Map<Integer, Integer> cnt = new HashMap<>();
private PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] == b[0] ? b[1] - a[1] : b[0] - a[0]);
private int ts;
public FreqStack() {
}
public void push(int val) {
cnt.put(val, cnt.getOrDefault(val, 0) + 1);
q.offer(new int[] {cnt.get(val), ++ts, val});
}
public int pop() {
int val = q.poll()[2];
cnt.put(val, cnt.get(val) - 1);
return val;
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(val);
* int param_2 = obj.pop();
*/class FreqStack {
private Map<Integer, Integer> cnt = new HashMap<>();
private Map<Integer, Deque<Integer>> d = new HashMap<>();
private int mx;
public FreqStack() {
}
public void push(int val) {
cnt.put(val, cnt.getOrDefault(val, 0) + 1);
int t = cnt.get(val);
d.computeIfAbsent(t, k -> new ArrayDeque<>()).push(val);
mx = Math.max(mx, t);
}
public int pop() {
int val = d.get(mx).pop();
cnt.put(val, cnt.get(val) - 1);
if (d.get(mx).isEmpty()) {
--mx;
}
return val;
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(val);
* int param_2 = obj.pop();
*/class FreqStack {
public:
FreqStack() {
}
void push(int val) {
++cnt[val];
q.emplace(cnt[val], ++ts, val);
}
int pop() {
auto [a, b, val] = q.top();
q.pop();
--cnt[val];
return val;
}
private:
unordered_map<int, int> cnt;
priority_queue<tuple<int, int, int>> q;
int ts = 0;
};
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/class FreqStack {
public:
FreqStack() {
}
void push(int val) {
++cnt[val];
d[cnt[val]].push(val);
mx = max(mx, cnt[val]);
}
int pop() {
int val = d[mx].top();
--cnt[val];
d[mx].pop();
if (d[mx].empty()) --mx;
return val;
}
private:
unordered_map<int, int> cnt;
unordered_map<int, stack<int>> d;
int mx = 0;
};
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/type FreqStack struct {
cnt map[int]int
q hp
ts int
}
func Constructor() FreqStack {
return FreqStack{map[int]int{}, hp{}, 0}
}
func (this *FreqStack) Push(val int) {
this.cnt[val]++
this.ts++
heap.Push(&this.q, tuple{this.cnt[val], this.ts, val})
}
func (this *FreqStack) Pop() int {
val := heap.Pop(&this.q).(tuple).val
this.cnt[val]--
return val
}
type tuple struct{ cnt, ts, val int }
type hp []tuple
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
return h[i].cnt > h[j].cnt || h[i].cnt == h[j].cnt && h[i].ts > h[j].ts
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
/**
* Your FreqStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* param_2 := obj.Pop();
*/type FreqStack struct {
cnt map[int]int
d map[int][]int
mx int
}
func Constructor() FreqStack {
return FreqStack{map[int]int{}, map[int][]int{}, 0}
}
func (this *FreqStack) Push(val int) {
this.cnt[val]++
this.d[this.cnt[val]] = append(this.d[this.cnt[val]], val)
this.mx = max(this.mx, this.cnt[val])
}
func (this *FreqStack) Pop() int {
val := this.d[this.mx][len(this.d[this.mx])-1]
this.d[this.mx] = this.d[this.mx][:len(this.d[this.mx])-1]
this.cnt[val]--
if len(this.d[this.mx]) == 0 {
this.mx--
}
return val
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
/**
* Your FreqStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* param_2 := obj.Pop();
*/