荥阳郑州网站建设,app开发公司哪,便宜购 网站建设,开发公司年终工作总结ppt1. 题目
我们把无限数量 ∞ 的栈排成一行#xff0c;按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。
实现一个叫「餐盘」的类 DinnerPlates#xff1a;
DinnerPlates(int capacity) - 给出栈的最大容量 capacity。void push(int val) - 将给出的正…1. 题目
我们把无限数量 ∞ 的栈排成一行按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。
实现一个叫「餐盘」的类 DinnerPlates
DinnerPlates(int capacity) - 给出栈的最大容量 capacity。void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。int pop() - 返回 从右往左第一个 非空栈顶部的值并将其从栈中删除如果所有的栈都是空的请返回 -1。int popAtStack(int index) - 返回编号 index 的栈顶部的值并将其从栈中删除如果编号 index 的栈是空的请返回 -1。
示例
输入
[DinnerPlates,push,push,push,push,push,popAtStack,push,push,
popAtStack,popAtStack,pop,pop,pop,pop,pop]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
输出
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]解释
DinnerPlates D DinnerPlates(2); // 初始化栈最大容量 capacity 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5); // 栈的现状为 2 41 3 5﹈ ﹈ ﹈
D.popAtStack(0); // 返回 2。栈的现状为 41 3 5﹈ ﹈ ﹈
D.push(20); // 栈的现状为 20 41 3 5﹈ ﹈ ﹈
D.push(21); // 栈的现状为 20 4 211 3 5﹈ ﹈ ﹈
D.popAtStack(0); // 返回 20。栈的现状为 4 211 3 5﹈ ﹈ ﹈
D.popAtStack(2); // 返回 21。栈的现状为 41 3 5﹈ ﹈ ﹈
D.pop() // 返回 5。栈的现状为 41 3 ﹈ ﹈
D.pop() // 返回 4。栈的现状为 1 3 ﹈ ﹈
D.pop() // 返回 3。栈的现状为 1 ﹈
D.pop() // 返回 1。现在没有栈。
D.pop() // 返回 -1。仍然没有栈。提示
1 capacity 20000
1 val 20000
0 index 100000
最多会对 pushpop和 popAtStack 进行 200000 次调用。来源力扣LeetCode 链接https://leetcode-cn.com/problems/dinner-plate-stacks 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
暴力法按题意进行逐个搜索超时
class STK//自定义栈
{
public:int size;int capacity;vectorint data;STK(int cap):size(0), capacity(cap) { data.resize(cap);}bool isEmpty() const { return size 0;}bool isFull() const { return capacity size;}void push(int val){if(!isFull())data[size] val;}int pop(){if(isEmpty())return -1;return data[--size];}
};
class DinnerPlates {int cap;vectorSTK v;
public:DinnerPlates(int capacity) {cap capacity;}void push(int val) {int i 0;while(i v.size() v[i].isFull())i;if(i v.size())v[i].push(val);else{v.push_back(STK(cap));v[i].push(val);}}int pop() {int i v.size()-1;while(i 0 v[i].isEmpty())i--;if(i 0)return -1;int tp v[i].pop();return tp;}int popAtStack(int index) {if(v.empty() || index v.size())return -1;return v[index].pop();}
};改进增加两个set , set 有序
setint s1;//存储没有满的栈的id
setint s2;//存储不为空的栈的ids1 的 begin() 就是可以 push 的 ids2 的 end()-- 就是可以 pop 的 id记得同时维护这两个 set
class STK//自定义栈
{
public:int size;int capacity;vectorint data;STK(int cap):size(0), capacity(cap) { data.resize(cap);}bool isEmpty() const { return size 0;}bool isFull() const { return capacity size;}void push(int val){if(!isFull())data[size] val;}int pop(){if(isEmpty())return -1;return data[--size];}
};
class DinnerPlates {int cap;vectorSTK v;setint s1;//存储没有满的栈的idsetint s2;//存储不为空的栈的idint tp;
public:DinnerPlates(int capacity) {cap capacity;}void push(int val) {if(!s1.empty()){v[*s1.begin()].push(val);s2.insert(*s1.begin());if(v[*s1.begin()].isFull())s1.erase(s1.begin());}else//所有的栈都满了{v.push_back(STK(cap));v[v.size()-1].push(val);s2.insert(v.size()-1);if(cap ! 1)s1.insert(v.size()-1);}}int pop() {if(s2.empty())//栈全部为空return -1;tp v[*(--s2.end())].pop();s1.insert(*(--s2.end()));if(v[*(--s2.end())].isEmpty())s2.erase(*(--s2.end()));return tp;}int popAtStack(int index) {if(v.empty() || index v.size())return -1;tp v[index].pop();if(v[index].isEmpty())s2.erase(index);s1.insert(index);return tp;}
};
