第六章 - 高频考题(困难)
0895. 最大频率栈

题目地址(895. 最大频率栈)

题目描述

1
实现 FreqStack,模拟类似栈的数据结构的操作的一个类。
2
3
FreqStack 有两个函数:
4
5
push(int x),将整数 x 推入栈中。
6
pop(),它移除并返回栈中出现最频繁的元素。
7
如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。
8
9
10
示例:
11
12
输入:
13
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
14
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
15
输出:[null,null,null,null,null,null,null,5,7,5,4]
16
解释:
17
执行六次 .push 操作后,栈自底向上为 [5,7,5,7,4,5]。然后:
18
19
pop() -> 返回 5,因为 5 是出现频率最高的。
20
栈变成 [5,7,5,7,4]。
21
22
pop() -> 返回 7,因为 5 和 7 都是频率最高的,但 7 最接近栈顶。
23
栈变成 [5,7,5,4]。
24
25
pop() -> 返回 5 。
26
栈变成 [5,7,4]。
27
28
pop() -> 返回 4 。
29
栈变成 [5,7]。
30
31
32
提示:
33
34
对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。
35
如果栈的元素数目为零,则保证不会调用 FreqStack.pop()。
36
单个测试样例中,对 FreqStack.push 的总调用次数不会超过 10000。
37
单个测试样例中,对 FreqStack.pop 的总调用次数不会超过 10000。
38
所有测试样例中,对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。
Copied!

前置知识

  • 设计题
  • 哈希表

公司

  • 暂无

思路

设计题目基本都是选择好数据结构,那么算法实现就会很容易。 如果你不会这道题,并去看其他人的题解代码,会发现很多时候都比较容易理解。 你没有能做出来的原因很大程度上是因为对基础数据结构不熟悉。设计题基本不太会涉及到算法,如果有算法, 也比较有限,常见的有二分法。
对于这道题来说,我们需要涉及一个栈。 这个栈弹出的不是最近压入栈的,而是频率最高的。
实际上,这已经不是栈了,只是它愿意这么叫。
既然要弹出频率最高的,那么我们肯定要统计所有栈中数字的出现频率。由于数字范围比较大,因此使用哈希表是一个不错的选择。为了能更快的求出频率最高的,我们需要将频率最高的数字(或者其出现次数)存起来。
另外题目要求如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。我们不妨就使用一个栈 fraq_stack 来维护,将相同频率的数字放到一个栈中。这样频率相同的我们直接出栈就可以取到最接近栈顶的元素啦。存储结构为:
1
{
2
3: [1,2,3],
3
2: [1,2,3,4],
4
1: [1,2,3,4,5]
5
}
Copied!
上面的结构表示 :
  • 1,2,3 出现了 3 次
  • 4 出现了 2 次
  • 5 出现了 1 次
细心的同学可能发现了,频率为 2 的列表中同样存储了频率更高(这里是频率为 3)的数字。
这是故意的。比如我们将 3 弹出,那么 3 其实就变成了频率为 2 的数字了。这个时候,我们如何将 3 插入到频率为 2 的栈的正确位置呢?其实你只要按照我上面的数据结构进行设计就没有这个问题啦。
我们以题目给的例子来讲解。
  • 使用 fraq 来存储对应的数字出现次数。key 是数字,value 频率
  • 由于题目限制“如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。”,我们考虑使用栈来维护一个频率表 fraq_stack。key 是频率,value 是数字组成的栈。
  • 同时用 max_fraq 记录当前的最大频率值。
  • 第一次 pop 的时候,我们最大的频率是 3。由 fraq_stack 知道我们需要 pop 掉 5。
  • 之后 pop 依次是这样的(红色数字表示顺序)

关键点解析

  • 栈的基本性质
  • hashtable 的基本性质
  • fraq_stack 的设计。fraq_stack 中当前频率的栈要保存所有大于等于其频率的数字
  • push 和 pop 的时候同时更新 fraq,max_fraq 和 fraq_stack。

代码

1
class FreqStack:
2
3
def __init__(self):
4
self.fraq = collections.defaultdict(lambda: 0)
5
self.fraq_stack = collections.defaultdict(list)
6
self.max_fraq = 0
7
8
def push(self, x: int) -> None:
9
self.fraq[x] += 1
10
if self.fraq[x] > self.max_fraq:
11
self.max_fraq = self.fraq[x]
12
self.fraq_stack[self.fraq[x]].append(x)
13
14
def pop(self) -> int:
15
ans = self.fraq_stack[self.max_fraq].pop()
16
self.fraq[ans] -= 1
17
if not self.fraq_stack[self.max_fraq]:
18
self.max_fraq -= 1
19
return ans
20
21
# Your FreqStack object will be instantiated and called as such:
22
# obj = FreqStack()
23
# obj.push(x)
24
# param_2 = obj.pop()
Copied!
复杂度分析
这里的复杂度为均摊复杂度。
  • 时间复杂度:$O(1)$
  • 空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。