【设计难题】力扣895-最大频率栈

  |  

摘要: 基于链表+哈希表解决与频数相关的设计问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文我们来看一个设计问题。需求与频数相关,具体地就是在栈的基础上,push 的操作不变,pop 的操作改为弹出栈中频数最多的元素,如果频数相同,还是弹出最接近栈顶的元素。

在文章 设计-功能系统 中我们系统梳理过设计功能系统的问题。本文解决的问题是一个基于链表+哈希表进行设计的。这种链表+哈希表的设计方法还是比较经典的,在前面的题目汇总中可以找到几个类似的题。此外本题还用到了按照频数对需要维护的信息进行分桶的做法,这也是是个常见操作,lc460、lc1224 等都用到了相同的操作。


$1 题目

895. 最大频率栈

实现 FreqStack,模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数:

push(int x),将整数 x 推入栈中。
pop(),它移除并返回栈中出现最频繁的元素。
如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。

提示:

1
2
3
4
5
对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。
如果栈的元素数目为零,则保证不会调用  FreqStack.pop()。
单个测试样例中,对 FreqStack.push 的总调用次数不会超过 10000。
单个测试样例中,对 FreqStack.pop 的总调用次数不会超过 10000。
所有测试样例中,对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。

示例:

输入:
[“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]
解释:
执行六次 .push 操作后,栈自底向上为 [5,7,5,7,4,5]。然后:

pop() -> 返回 5,因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7,因为 5 和 7 都是频率最高的,但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

$2 题解

算法1: 链表+哈希表+频数桶

  • list<int> 维护栈的逻辑和元素。
  • 频率桶 vector<list<Bag>> 维护特定频数下的各个元素的信息,Bag 是维护一个元素的信息的结构,其信息包括元素值本身,以及它在链表 list<int> 中出现的位置。
  • 哈希表联系 list<int> 中的元素和该元素在 vector<list<Bag>> 中的位置。
  • 维护全局时间戳,用于对比频率相同时候哪个元素排在前面。

设计细节详见代码中 private 的部分。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class FreqStack {
public:
FreqStack() {
cnts = vector<list<Bag>>(1);
stamp = 0;
st = list<int>();
mapping = unordered_map<int, list<Bag>::iterator>();
}

void push(int x) {
st.push_back(x);
list<int>::iterator item_it = --st.end();
if(mapping.count(x))
{
list<Bag>::iterator it = mapping[x];
int cnt = (it -> items) -> size();
(it -> items) -> push_front(Item(stamp++, item_it));
Bag new_item(x, it -> items);
if((int)cnts.size() == cnt + 1)
cnts.push_back({});
cnts[cnt + 1].push_front(new_item);
cnts[cnt].erase(it);
mapping[x] = cnts[cnt + 1].begin();
}
else
{
if((int)cnts.size() == 1)
cnts.push_back({});
list<Item> *l = new list<Item>(1, Item(stamp++, item_it));
cnts[1].push_front(Bag(x, l));
mapping[x] = cnts[1].begin();
}
}

int pop() {
int cnt = cnts.size() - 1;
// 找到待删除元素:删除 st 中最靠近顶的 x
int x = cnts[cnt].front().x;
list<int>::iterator item_it = (cnts[cnt].front().items -> front()).it;
// 创建 new_item 后删除 cnts[cnt].front()
cnts[cnt].front().items -> pop_front();
Bag new_item(x, cnts[cnt].front().items);
cnts[cnt].pop_front();
if(cnts[cnt].empty())
cnts.pop_back();
// 若 cnt -1 >= 1
// 在 cnts[cnt - 1] 中找到插入 new_item 的位置
if(cnt >= 2)
{
auto it = cnts[cnt - 1].begin();
while(it != cnts[cnt - 1].end() && (it -> items -> front()).stamp > (new_item.items -> front()).stamp)
++it;
it = cnts[cnt - 1].insert(it, new_item);
mapping[x] = it;
}
else
mapping.erase(x);
st.erase(item_it);
return x;
}

private:
struct Item
{
int stamp;
list<int>::iterator it;
Item(int stamp, list<int>::iterator it):stamp(stamp),it(it){}
};

struct Bag
{
int x;
list<Item> *items;
Bag(int x=-1, list<Item>* items=nullptr):x(x),items(items){}
};

int stamp;
list<int> st;
unordered_map<int, list<Bag>::iterator> mapping;
vector<list<Bag>> cnts;
};

算法2: 每个频数维护一个栈

  • 哈希表维护元素和元素频数的联系
  • 频数桶维护特定频数下的各个元素,用栈维护顺序。桶内的栈只保存使得频数为当前值的那一个元素,例如如果一个元素 x 的频数是 f,则在 1 ~ f-1 的桶中也会有 x 这个元素。

设计细节详见代码中 private 的部分。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class FreqStack {
public:
FreqStack() {
cnts = vector<stack<int>>(1);
}

void push(int x) {
++mapping[x];
int cnt = mapping[x];
if((int)cnts.size() == cnt)
cnts.push_back({});
cnts[cnt].push(x);
}

int pop() {
int cnt = cnts.size() - 1;
int x = cnts[cnt].top();
cnts[cnt].pop();
if(cnts[cnt].empty())
cnts.pop_back();
--mapping[x];
return x;
}

private:
vector<stack<int>> cnts;
unordered_map<int, int> mapping;
};

Share