网站建设caiyiduo,响应式网站建设服务商,宁波网站建设公司制作网站,网站搭建三部曲是什么?优先队列
解题思路#xff1a;根据题意模拟。用数组存储无限数量的栈。重在实现 p u s h push push 和 p o p pop pop 操作。
对于 p u s h push push 操作#xff0c;需要知道当前从左往右第一个空栈的下标。分两类讨论#xff1a; ①所有栈都是满的#xff0c;那么我…优先队列
解题思路根据题意模拟。用数组存储无限数量的栈。重在实现 p u s h push push 和 p o p pop pop 操作。
对于 p u s h push push 操作需要知道当前从左往右第一个空栈的下标。分两类讨论 ①所有栈都是满的那么我们创建一个新栈新栈存 p u s h push push 进来的值再将新栈加入数组尾部。 ②已存在的某些栈未满那么从左往右遍历数组找到第一个未满的栈第一个未满的栈存 p u s h push push 进来的值。
这样一来我们发现每个 p u s h push push 的操作②的最坏平均时间复杂度 O ( n ) O(n) O(n) 一共 n n n 个 p u s h push push 总体时间复杂度 O ( n 2 ) O(n^2) O(n2)题目给出 p u s h push push 操作最多调用 2 × 1 0 5 2 \times 10 ^ 5 2×105 次时间 O ( n 2 ) O(n^2) O(n2) 必然超时。
操作②既然是遍历有一个直观的优化方法用优先队列小根堆存储未满栈的下标。这样以来维护未满的栈的时间复杂度就是 O ( l o g n ) O(logn) O(logn)每次维护完毕堆顶就是最小下标。总体时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)可以接受。 对于 p o p pop pop 操作它等价于 p o p A t S t a c k popAtStack popAtStack 操作将参数 i n d e x index index 设为数组最后位置。 对于 p o p A t S t a c k popAtStack popAtStack 操作简单模拟即可。
提示对于优先队列的维护请思考边界。也可以看代码注释。
class DinnerPlates {
public:int capacity;vectorstackint S;priority_queueint, vectorint, greaterint pq; // 维护未满栈的下标DinnerPlates(int capacity) {this-capacity capacity;}void push(int val) {if (pq.size() pq.top() S.size()) { // 清空越界下标pq priority_queueint, vectorint, greaterint();}// while (pq.size() pq.top() S.size()) pq.pop(); // 清空越界下标if (pq.empty()) { // 插入新栈stackint ts;ts.push(val);if (capacity 1) pq.push(S.size());S.push_back(ts);} else { // 插入第一个未满栈int pos pq.top();S[pos].push(val);if (S[pos].size() capacity) { // 插入后栈满pq.pop(); // 下标弹栈}}}int pop() {return popAtStack(S.size() - 1);}int popAtStack(int index) {if (index S.size() || S[index].empty()) {return -1;} else {int ans S[index].top();S[index].pop();if (S[index].size() capacity - 1) pq.push(index);while (S.size() S.back().empty()) S.pop_back();return ans;}}
};时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) : 一共 n n n 次操作每个操作的时间复杂度 O ( l o g n ) O(logn) O(logn) 时间瓶颈在于维护堆。总体时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( n ) O(n) O(n) : 优先队列、栈的最坏空间复杂度 O ( n ) O(n) O(n)
AC 致语
理解思路很重要读者有问题请留言清墨看到就会回复的。
