1172. 餐盘栈
==Hard==
我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 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。仍然没有栈。
题解
方法一：栈数组 + 有序集合
我们定义以下数据结构或变量：
capacity：每个栈的容量；stacks：栈数组，用于存储所有的栈，其中每个栈的最大容量都是capacity；not_full：有序集合，用于存储所有未满的栈在栈数组中的下标。
对于 push(val) 操作：
- 我们首先判断
not_full是否为空，如果为空，则说明没有未满的栈，需要新建一个栈，然后将val压入该栈中，此时判断容量capacity是否大于 1，如果大于 1，则将该栈的下标加入not_full中。 - 如果
not_full不为空，则说明有未满的栈，我们取出not_full中最小的下标index，将val压入stacks[index]中，此时如果stacks[index]的容量等于capacity，则将index从not_full中删除。
对于 popAtStack(index) 操作：
- 我们首先判断
index是否在stacks的下标范围内，如果不在，则直接返回 −1。如果stacks[index]为空，同样直接返回 −1。 - 如果
stacks[index]不为空，则弹出stacks[index]的栈顶元素val。如果index等于stacks的长度减 1，则说明stacks[index]是最后一个栈，如果为空，我们循环将最后一个栈的下标从not_full中移出，并且在栈数组stacks中移除最后一个栈，直到最后一个栈不为空、或者栈数组stacks为空为止。否则，如果stacks[index]不是最后一个栈，我们将index加入not_full中。 - 最后返回
val。
对于 pop() 操作：
- 我们直接调用
popAtStack(stacks.length - 1)即可。
class DinnerPlates {
public:
DinnerPlates(int capacity) {
this->capacity = capacity;
}
// 插入元素，push 方法会将元素插入到最早有空闲栈的末尾或者新建一个栈
void push(int val) {
// 如果不存在有空闲栈，就新建一个栈，并把元素压入
if (notFull.empty()) {
stacks.emplace_back(stack());
stacks.back().push(val);
// 如果栈的容量大于 1，那么表示该栈还有余地，需要将其纳入有空闲栈的集合
if (capacity > 1) {
notFull.insert(stacks.size() - 1);
}
} else {
// 否则，找到有空闲栈中的最小索引，将元素压入到该栈的末尾
// 注意，这里的索引是集合中最小的索引，而不是数组下标
int index = *notFull.begin();
stacks[index].push(val);
if (stacks[index].size() == capacity) {
// 如果当前栈已经达到容量上限，就将其从集合中移除
notFull.erase(index);
}
}
}
// 弹出最后一个栈的栈顶元素，如果没有任何元素就返回 -1
int pop() {
return popAtStack(stacks.size() - 1);
}
// 弹出指定栈的栈顶元素，如果栈为空或者索引越界就返回 -1
int popAtStack(int index) {
if (index < 0 || index >= stacks.size() || stacks[index].empty()) {
// 如果索引越界或者栈为空，就返回 -1
return -1;
}
// 否则，弹出该栈的栈顶元素，并检查该栈是否已经空了
int val = stacks[index].top();
stacks[index].pop();
if (index == stacks.size() - 1 && stacks[index].empty()) {
// 如果当前弹出的是最后一个栈的元素，并且该栈已经空了，
// 就需要将数组末尾也为空的栈移除掉，同时更新有空闲栈的集合
while (!stacks.empty() && stacks.back().empty()) {
notFull.erase(stacks.size() - 1);
stacks.pop_back();
}
} else {
// 如果弹出的是中间的某个栈的元素，就将其索引加入到有空闲栈的集合之中
notFull.insert(index);
}
return val;
}
private:
int capacity; // 定义栈的容量
vector> stacks; // 维护多个栈
set notFull; // 存储有空闲栈的索引
};
/**
* Your DinnerPlates object will be instantiated and called as such:
* DinnerPlates* obj = new DinnerPlates(capacity);
* obj->push(val);
* int param_2 = obj->pop();
* int param_3 = obj->popAtStack(index);
*/