三个栈实现最大队列

用三个栈 s1 s2 s3 实现队列。

• push：在队尾插入一个元素。
• pop：删除并返回队头元素，若没有元素则返回 -1。
• max_value：返回整个队列中最大的元素，要求时间复杂度 $O(1)$。

可以直接使用操作栈的函数。

解题

思路

• 栈模拟队列，s1 作为压入栈，s2 作为弹出栈。
• 而 $O(1)$ 返回最大值可以用单调栈

复杂度

只用到了三个栈，所以空间复杂度全为 $O(n)$。

push、max_value 以及构造器均为 $O(1)$。

对于 pop 来说

• 当 s2 不为空时直接弹出。此时，时间复杂度为 $O(1)$。
• 当 s2 为空时会将 s1 全部弹出到 s2，而对 s1 的元素来说只会移动一次进入 s2。所以和情况一均摊时间复杂度为 $O(1)$.

代码

class 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;
}
};

对数器

int 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：

输入：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(NlogN)$，建堆需要 $O(NlogN)$，push 和 pop 分别要 $O(log)$，需要 push 和 pop 共 $3(n-1)$ 次。

空间复杂度 $O(1)$

代码

class 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 年哈工大 854 算法大题三个栈实现最大队列连接棒材的最低费用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。