使用C++解决这个问题:1172. 餐盘栈 提示 困难 96 相关企业 我们把无限数量 ∞ 的栈排成一行,按从左到右的次序从 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 4 1 3 5 ﹈ ﹈ ﹈ D.popAtStack(0); // 返回 2。栈的现状为: 4 1 3 5 ﹈ ﹈ ﹈ D.push(20); // 栈的现状为: 20 4 1 3 5 ﹈ ﹈ ﹈ D.push(21); // 栈的现状为: 20 4 21 1 3 5 ﹈ ﹈ ﹈ D.popAtStack(0); // 返回 20。栈的现状为: 4 21 1 3 5 ﹈ ﹈ ﹈ D.popAtStack(2); // 返回 21。栈的现状为: 4 1 3 5 ﹈ ﹈ ﹈ D.pop() // 返回 5。栈的现状为: 4 1 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 最多会对 push,pop,和 popAtStack 进行 200000 次调用。
时间: 2024-01-21 09:16:24 浏览: 15
这个问题可以使用 C++ 的 vector 来实现。我们可以定义一个 vector 数组来存储所有的栈,每一个栈都有一个当前的容量和最大容量。同时,我们还需要维护一个变量 max_stacks 来表示当前最大的栈编号。
对于 push 操作,我们从左往右遍历所有的栈,找到第一个未满的栈,将元素加入该栈中。如果所有的栈都已经满了,我们就新建一个栈,并将元素加入该栈中。
对于 pop 操作,我们从右往左遍历所有的栈,找到第一个非空的栈,弹出该栈的栈顶元素,并将该栈从 vector 中删除。如果所有的栈都是空的,我们就返回 -1。
对于 popAtStack 操作,我们先检查编号 index 是否有效(即 index < max_stacks)。如果不是,我们就返回 -1。否则,我们从 vector 中取出编号为 index 的栈,弹出该栈的栈顶元素,如果该栈已经为空,我们就将该栈从 vector 中删除。注意,即使该栈被删除了,我们仍然需要更新 max_stacks。
下面是完整的 C++ 代码实现:
```c++
#include <vector>
#include <iostream>
using namespace std;
class DinnerPlates {
public:
DinnerPlates(int capacity) {
this->capacity = capacity;
this->max_stacks = 0;
}
void push(int val) {
if (!stacks.empty()) {
for (int i = 0; i < stacks.size(); i++) {
if (stacks[i].size() < capacity) {
stacks[i].push_back(val);
return;
}
}
}
stacks.push_back(vector<int>());
stacks[stacks.size()-1].push_back(val);
max_stacks++;
}
int pop() {
if (stacks.empty()) {
return -1;
}
for (int i = stacks.size()-1; i >= 0; i--) {
if (!stacks[i].empty()) {
int val = stacks[i].back();
stacks[i].pop_back();
if (stacks[i].empty() && i == max_stacks-1) {
max_stacks--;
}
return val;
}
}
return -1;
}
int popAtStack(int index) {
if (index >= max_stacks || stacks[index].empty()) {
return -1;
}
int val = stacks[index].back();
stacks[index].pop_back();
if (stacks[index].empty() && index == max_stacks-1) {
max_stacks--;
}
return val;
}
private:
vector<vector<int>> stacks;
int capacity;
int max_stacks;
};
int main() {
DinnerPlates d(2);
d.push(1);
d.push(2);
d.push(3);
d.push(4);
d.push(5);
cout << d.popAtStack(0) << endl;
d.push(20);
d.push(21);
cout << d.popAtStack(0) << endl;
cout << d.popAtStack(2) << endl;
cout << d.pop() << endl;
cout << d.pop() << endl;
cout << d.pop() << endl;
cout << d.pop() << endl;
cout << d.pop() << endl;
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)