三个栈实现最大队列
用三个栈 s1 s2 s3 实现队列。
- push：在队尾插入一个元素。
- pop：删除并返回队头元素，若没有元素则返回 -1。
- max_value：返回整个队列中最大的元素，要求时间复杂度 O ( 1 ) O(1) O(1)。
可以直接使用操作栈的函数。
解题
思路
- 栈模拟队列，s1 作为压入栈，s2 作为弹出栈。
- 而 O ( 1 ) O(1) O(1) 返回最大值可以用单调栈
复杂度
只用到了三个栈，所以空间复杂度全为 O ( n ) O(n) O(n)。
push、max_value 以及构造器均为
O
(
1
)
O(1)
O(1)。
对于 pop 来说
- 当 s2 不为空时直接弹出。此时，时间复杂度为 O ( 1 ) O(1) O(1)。
- 当 s2 为空时会将 s1 全部弹出到 s2，而对 s1 的元素来说只会移动一次进入 s2。所以和情况一均摊时间复杂度为 O ( 1 ) O(1) O(1).
| push | pop | max_value | |
|---|---|---|---|
| 时间复杂度 | O ( 1 ) O(1) O(1) | 均摊 O ( 1 ) O(1) O(1) | O ( 1 ) O(1) O(1) |
| 空间复杂度 | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) | O ( n ) O(n) O(n) |
代码
复制代码
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
32class max_queue { private: stack<int> s1, s2, s3; int mx = INT_MIN; public: max_queue() { s3.push(mx); } int max_value() { if (s1.empty() and s2.empty()) return -1; else return max(mx, s3.top()); } void push(int x) { s1.push(x); mx = max(mx, x); } int pop() { if (s2.empty()) { if (s1.empty()) return -1; while (!s1.empty()) { int x = s1.top(); s1.pop(); s2.push(x); if (x >= s3.top()) s3.push(x); } mx = INT_MIN; } int res = s2.top(); s2.pop(); if (res == s3.top()) s3.pop(); return res; } };
对数器
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25int force(queue<int> q) { // 将整个队列排序，然后取得最大值。这个解法保证正确。 vector<int> v; while (q.size()) v.push_back(q.front()), q.pop(); sort(v.begin(), v.end()); return v[v.size() - 1]; } #define N 100000 // 进行十万次 pop 或 push 操作 int main(int argc, const char * argv[]) { queue<int> q1; max_queue q2; for (int i = 0; i < N; i++) { int r = rand(); if (r % 2 && q1.size()) { if (force(q1) != q2.max_value()) cout << "Oops 1" << endl; // 最大值对比 if (q1.front() != q2.pop()) cout << "Oops 2" << endl; // 弹出结果对比 q1.pop(); } else { r %= 9; q1.push(r), q2.push(r); } } cout << "AC" << endl; // 输出 AC 表明代码实现正确 return 0; }
连接棒材的最低费用
这道题是一个算法设计题，只要求阐述思想算出复杂度，不要求代码实现。leetcode 原题。
另外一到算法设计题是个水题没啥好说的。
为了装修新房，你需要加工一些长度为正整数的棒材 。棒材以数组 sticks 的形式给出，其中 sticks[i]是第 i 根棒材的长度。
如果要将长度分别为 x 和 y 的两根棒材连接在一起，你需要支付 x + y 的费用。 由于施工需要，你必须将所有棒材连接成一根。
返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。
示例 1：
复制代码
1
2
3
4
5
6
7输入：sticks = [2,4,3] 输出：14 解释：从 sticks = [2,4,3] 开始。 1. 连接 2 和 3 ，费用为 2 + 3 = 5 。现在 sticks = [5,4] 2. 连接 5 和 4 ，费用为 5 + 4 = 9 。现在 sticks = [9] 所有棒材已经连成一根，总费用 5 + 9 = 14
解法：小顶堆
思路
高端的名词，哈夫曼编码。好的你现在懂了。
其实就是个贪心，先把两个小元素合成一个大元素，再把这个大元素放在一起，再从里面挑俩个小元素，直到合成一个大元素。
用一个优先队列（堆）就搞定了。
复杂度
时间复杂度
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)，建堆需要
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)，push 和 pop 分别要
O
(
l
o
g
)
O(log)
O(log)，需要 push 和 pop 共
3
(
n
−
1
)
3(n-1)
3(n−1) 次。
空间复杂度 O ( 1 ) O(1) O(1)
代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution { public: int connectSticks(vector<int>& s) { priority_queue <int, vector <int>, greater <int> > q(s.begin(), s.end()); int res = 0; while (q.size() > 1) { int x = q.top(); q.pop(); int y = q.top(); q.pop(); res += x + y; q.push(x + y); } return res; } };
最后
以上就是无辜小刺猬最近收集整理的关于2022 年哈工大 854 算法大题三个栈实现最大队列连接棒材的最低费用的全部内容，更多相关2022内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复