Hard
题目描述
设计一个类似栈的数据结构，将元素推入栈中，从栈中弹出出现频率最高的元素。
实现 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 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 <= 10^9push和pop的操作数不大于2 * 10^4。- 输入保证在调用
pop之前栈中至少有一个元素。
解题思路
解题思路
这道题需要设计一个频率栈，关键在于如何高效地维护频率信息和栈的性质。
核心思路
我们需要同时维护两个信息：
- 每个元素的出现频率
- 相同频率下元素的入栈顺序
关键观察：我们可以将问题转化为按频率分层的栈结构。每个频率层维护一个独立的栈。
数据结构设计
freq哈希表：记录每个元素的当前频率stacks哈希表：以频率为键，栈为值，存储该频率下的所有元素maxFreq变量：记录当前最大频率
操作流程
Push操作：
- 增加元素的频率计数
- 将元素推入对应频率的栈中
- 更新最大频率
Pop操作：
- 从最大频率的栈顶弹出元素
- 减少该元素的频率计数
- 如果最大频率的栈为空，减少maxFreq
这种方法巧妙地利用了栈的LIFO特性来处理"最接近栈顶"的要求，同时通过频率分层确保总是弹出频率最高的元素。
时间复杂度为O(1)，空间复杂度为O(N)，是最优解法。
代码实现
class FreqStack {
public:
unordered_map<int, int> freq;
unordered_map<int, stack<int>> stacks;
int maxFreq;
FreqStack() {
maxFreq = 0;
}
void push(int val) {
freq[val]++;
stacks[freq[val]].push(val);
maxFreq = max(maxFreq, freq[val]);
}
int pop() {
int val = stacks[maxFreq].top();
stacks[maxFreq].pop();
freq[val]--;
if (stacks[maxFreq].empty()) {
maxFreq--;
}
return val;
}
};
class FreqStack:
def __init__(self):
self.freq = {}
self.stacks = {}
self.max_freq = 0
def push(self, val: int) -> None:
self.freq[val] = self.freq.get(val, 0) + 1
f = self.freq[val]
if f not in self.stacks:
self.stacks[f] = []
self.stacks[f].append(val)
self.max_freq = max(self.max_freq, f)
def pop(self) -> int:
val = self.stacks[self.max_freq].pop()
self.freq[val] -= 1
if not self.stacks[self.max_freq]:
self.max_freq -= 1
return val
public class FreqStack {
private Dictionary<int, int> freq;
private Dictionary<int, Stack<int>> stacks;
private int maxFreq;
public FreqStack() {
freq = new Dictionary<int, int>();
stacks = new Dictionary<int, Stack<int>>();
maxFreq = 0;
}
public void Push(int val) {
if (!freq.ContainsKey(val)) {
freq[val] = 0;
}
freq[val]++;
int f = freq[val];
if (!stacks.ContainsKey(f)) {
stacks[f] = new Stack<int>();
}
stacks[f].Push(val);
maxFreq = Math.Max(maxFreq, f);
}
public int Pop() {
int val = stacks[maxFreq].Pop();
freq[val]--;
if (stacks[maxFreq].Count == 0) {
maxFreq--;
}
return val;
}
}
var FreqStack = function() {
this.freq = new Map();
this.group = new Map();
this.maxfreq = 0;
};
FreqStack.prototype.push = function(val) {
let f = this.freq.get(val) || 0;
f++;
this.freq.set(val, f);
this.maxfreq = Math.max(this.maxfreq, f);
if (!this.group.has(f)) {
this.group.set(f, []);
}
this.group.get(f).push(val);
};
FreqStack.prototype.pop = function() {
let x = this.group.get(this.maxfreq).pop();
this.freq.set(x, this.freq.get(x) - 1);
if (this.group.get(this.maxfreq).length === 0) {
this.maxfreq--;
}
return x;
};
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| Push | O(1) | O(N) |
| Pop | O(1) | O(N) |
其中 N 是栈中元素的总数。空间复杂度主要由频率哈希表和各频率层的栈所占用。