895. 最大频率栈
设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
实现 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 之前堆栈中至少有一个元素。原站题解
java 解法, 执行用时: 33 ms, 内存消耗: 50.8 MB, 提交时间: 2022-12-04 17:53:31
class FreqStack {
private Map<Integer, Integer> freq;
private Map<Integer, Deque<Integer>> group;
private int maxFreq;
public FreqStack() {
freq = new HashMap<Integer, Integer>();
group = new HashMap<Integer, Deque<Integer>>();
maxFreq = 0;
}
public void push(int val) {
freq.put(val, freq.getOrDefault(val, 0) + 1);
group.putIfAbsent(freq.get(val), new ArrayDeque<Integer>());
group.get(freq.get(val)).push(val);
maxFreq = Math.max(maxFreq, freq.get(val));
}
public int pop() {
int val = group.get(maxFreq).peek();
freq.put(val, freq.get(val) - 1);
group.get(maxFreq).pop();
if (group.get(maxFreq).isEmpty()) {
maxFreq--;
}
return val;
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(val);
* int param_2 = obj.pop();
*/
java 解法, 执行用时: 26 ms, 内存消耗: 50.5 MB, 提交时间: 2022-12-04 17:53:12
class FreqStack {
private final Map<Integer, Integer> cnt = new HashMap<>();
private final List<Deque<Integer>> stacks = new ArrayList<>();
public void push(int val) {
int c = cnt.getOrDefault(val, 0);
if (c == stacks.size()) // 这个元素的频率已经是目前最多的，现在又出现了一次
stacks.add(new ArrayDeque<>()); // 那么必须创建一个新栈
stacks.get(c).push(val);
cnt.put(val, c + 1); // 更新频率
}
public int pop() {
int back = stacks.size() - 1;
int val = stacks.get(back).pop(); // 弹出最右侧栈的栈顶
if (stacks.get(back).isEmpty()) // 栈为空
stacks.remove(back); // 删除
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();
*/
golang 解法, 执行用时: 144 ms, 内存消耗: 9.8 MB, 提交时间: 2022-12-04 17:52:55
type FreqStack struct {
cnt map[int]int
stacks [][]int
}
func Constructor() FreqStack {
return FreqStack{cnt: map[int]int{}}
}
func (f *FreqStack) Push(val int) {
c := f.cnt[val]
if c == len(f.stacks) { // 这个元素的频率已经是目前最多的，现在又出现了一次
f.stacks = append(f.stacks, []int{val}) // 那么必须创建一个新栈
} else {
f.stacks[c] = append(f.stacks[c], val) // 否则就压入对应的栈
}
f.cnt[val]++ // 更新频率
}
func (f *FreqStack) Pop() int {
back := len(f.stacks) - 1
st := f.stacks[back]
bk := len(st) - 1
val := st[bk] // 弹出最右侧栈的栈顶
if bk == 0 { // 栈为空
f.stacks = f.stacks[:back] // 删除
} else {
f.stacks[back] = st[:bk]
}
f.cnt[val]-- // 更新频率
return val
}
/**
* Your FreqStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* param_2 := obj.Pop();
*/
python3 解法, 执行用时: 272 ms, 内存消耗: 23.2 MB, 提交时间: 2022-12-04 17:52:33
class FreqStack:
def __init__(self):
self.cnt = Counter()
self.stacks = [] # 每个元素都是一个栈
def push(self, val: int) -> None:
if self.cnt[val] == len(self.stacks): # 这个元素的频率已经是目前最多的，现在又出现了一次
self.stacks.append([val]) # 那么必须创建一个新栈
else:
self.stacks[self.cnt[val]].append(val) # 否则就压入对应的栈
self.cnt[val] += 1 # 更新频率
def pop(self) -> int:
val = self.stacks[-1].pop() # 弹出最右侧栈的栈顶
if len(self.stacks[-1]) == 0: # 栈为空
self.stacks.pop() # 删除
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()
golang 解法, 执行用时: 140 ms, 内存消耗: 9.8 MB, 提交时间: 2022-11-30 10:40:35
type FreqStack struct {
freq map[int]int
group map[int][]int
maxFreq int
}
func Constructor() FreqStack {
return FreqStack{map[int]int{}, map[int][]int{}, 0}
}
func (f *FreqStack) Push(val int) {
f.freq[val]++
f.group[f.freq[val]] = append(f.group[f.freq[val]], val)
f.maxFreq = max(f.maxFreq, f.freq[val])
}
func (f *FreqStack) Pop() int {
val := f.group[f.maxFreq][len(f.group[f.maxFreq])-1]
f.group[f.maxFreq] = f.group[f.maxFreq][:len(f.group[f.maxFreq])-1]
f.freq[val]--
if len(f.group[f.maxFreq]) == 0 {
f.maxFreq--
}
return val
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
/**
* Your FreqStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* param_2 := obj.Pop();
*/
javascript 解法, 执行用时: 460 ms, 内存消耗: 64 MB, 提交时间: 2022-11-30 10:40:12
var FreqStack = function() {
this.freq = new Map();
this.group = new Map();
this.maxFreq = 0;
};
/**
* @param {number} val
* @return {void}
*/
FreqStack.prototype.push = function(val) {
this.freq.set(val, (this.freq.get(val) || 0) + 1);
if (!this.group.has(this.freq.get(val))) {
this.group.set(this.freq.get(val), []);
}
this.group.get(this.freq.get(val)).push(val);
this.maxFreq = Math.max(this.maxFreq, this.freq.get(val));
};
/**
* @return {number}
*/
FreqStack.prototype.pop = function() {
const val = this.group.get(this.maxFreq)[this.group.get(this.maxFreq).length - 1];
this.freq.set(val, this.freq.get(val) - 1);
this.group.get(this.maxFreq).pop();
if (this.group.get(this.maxFreq).length === 0) {
this.maxFreq--;
}
return val;
};
/**
* Your FreqStack object will be instantiated and called as such:
* var obj = new FreqStack()
* obj.push(val)
* var param_2 = obj.pop()
*/
python3 解法, 执行用时: 272 ms, 内存消耗: 23.2 MB, 提交时间: 2022-11-30 10:39:22
class FreqStack:
def __init__(self):
self.freq = defaultdict(int)
self.group = defaultdict(list)
self.maxFreq = 0
def push(self, val: int) -> None:
self.freq[val] += 1
self.group[self.freq[val]].append(val)
self.maxFreq = max(self.maxFreq, self.freq[val])
def pop(self) -> int:
val = self.group[self.maxFreq].pop()
self.freq[val] -= 1
if len(self.group[self.maxFreq]) == 0:
self.maxFreq -= 1
return val
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
golang 解法, 执行用时: 204 ms, 内存消耗: 10 MB, 提交时间: 2022-11-30 10:37:03
type FreqStack struct {
cnt map[int]int
stacks [][]int
}
func Constructor() FreqStack {
return FreqStack{cnt: map[int]int{}}
}
func (f *FreqStack) Push(val int) {
c := f.cnt[val]
if c == len(f.stacks) { // 这个元素的频率已经是目前最多的，现在又出现了一次
f.stacks = append(f.stacks, []int{val}) // 那么必须创建一个新栈
} else {
f.stacks[c] = append(f.stacks[c], val) // 否则就压入对应的栈
}
f.cnt[val]++ // 更新频率
}
func (f *FreqStack) Pop() int {
back := len(f.stacks) - 1
st := f.stacks[back]
bk := len(st) - 1
val := st[bk] // 弹出最右侧栈的栈顶
if bk == 0 { // 栈为空
f.stacks = f.stacks[:back] // 删除
} else {
f.stacks[back] = st[:bk]
}
f.cnt[val]-- // 更新频率
return val
}
/**
* Your FreqStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* param_2 := obj.Pop();
*/
python3 解法, 执行用时: 284 ms, 内存消耗: 22.9 MB, 提交时间: 2022-11-30 10:36:44
class FreqStack:
def __init__(self):
self.cnt = Counter()
self.stacks = [] # 每个元素都是一个栈
def push(self, val: int) -> None:
if self.cnt[val] == len(self.stacks): # 这个元素的频率已经是目前最多的，现在又出现了一次
self.stacks.append([val]) # 那么必须创建一个新栈
else:
self.stacks[self.cnt[val]].append(val) # 否则就压入对应的栈
self.cnt[val] += 1 # 更新频率
def pop(self) -> int:
val = self.stacks[-1].pop() # 弹出最右侧栈的栈顶
if len(self.stacks[-1]) == 0: # 栈为空
self.stacks.pop() # 删除
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()