title
我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 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 <= 200001 <= val <= 200000 <= index <= 100000- 最多会对
push，pop，和popAtStack进行200000次调用。
solution
难点在于动态的找左边第一个未满的，然后还中间操作。
尽量不要用线段树，即使线段树可行，但会卡常超时。
用sortedlist维护not_full的位置即可。
class DinnerPlates:
def __init__(self, capacity: int):
self.stack = []
import sortedcontainers
self.not_full = sortedcontainers.SortedList()
self.capacity = capacity
def push(self, val: int) -> None:
if not self.not_full:
self.stack.append([val])
if self.capacity > 1:
self.not_full.add(len(self.stack)-1)
else:
# print(val, self.not_full, self.stack)
self.stack[self.not_full[0]].append(val)
if len(self.stack[self.not_full[0]]) == self.capacity:
del self.not_full[0]
def pop(self) -> int:
if not self.stack:
return -1
return self.popAtStack(len(self.stack) - 1)
def popAtStack(self, index: int) -> int:
# print(index, self.stack, self.not_full)
if index >= len(self.stack) or not self.stack[index]:
return -1
if len(self.stack[index]) == self.capacity and self.capacity -1 >= 0:
self.not_full.add(index)
res = self.stack[index].pop()
if index == len(self.stack) -1 and not self.stack[-1]:
while self.stack and not self.stack[-1]:
self.not_full.discard(len(self.stack)-1)
self.stack.pop()
return res