题目描述
我们把无限数量的栈排成一行,按从左到右的次序从 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
次调用。
算法
(栈,有序集合) $O(n \log n)$
- 我们用
vector
定义二维数组,第一维代表每个盘子栈,第二维是每个stack
上的盘子。用变量top
表示当前最大的有盘子栈的位置,初始为-1
。 - 同时,我们使用一个有序集合
non_full_stack
,记录当前没有满的盘子栈的下标,初始为空。 - 对于插入操作,如果
non_full_stack
为空,则++top
,新创建一个盘子栈,将下标放入non_full_stack
中。从集合中取出最小的位置,然后插入新盘子,更新top
和non_full_stack
。 - 对于
pop
操作,直接进行popAtStack(top)
。 - 对于
popAtStack
操作,如果给定的index
为-1
或者 超出了当前数组的范围,则返回-1
。如果给定的位置上盘子数为空,也返回-1
。在弹出对应位置的盘子后,如果那个位置上盘子数量为capacity - 1
,则可以在有序集合中插入这个位置。最后,如果当前位置为空,则不断的更新top
,直到一个不为空的位置。
时间复杂度
- 每次插入操作,查询有序集合,故时间复杂度为 $O(\log n)$,其中 $n$ 为操作的数量。
- 对于弹出操作,插入有序集合,故时间复杂度也为 $O(\log n)$。更新
top
的操作均摊下来也是常数的复杂度。 - 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要二维数组和有序集合分别存放盘子和位置,故空间复杂度为 $O(n)$。
C++ 代码
class DinnerPlates {
public:
vector<vector<int>> plates;
int top;
set<int> non_full_stack;
int capacity;
DinnerPlates(int capacity) {
top = -1;
this -> capacity = capacity;
}
void push(int val) {
if (non_full_stack.empty()) {
non_full_stack.insert(++top);
plates.push_back(vector<int>());
}
auto left_most = non_full_stack.begin();
int idx = *left_most;
auto &s = plates[idx];
if (idx > top)
top = idx;
s.push_back(val);
if (s.size() == capacity)
non_full_stack.erase(left_most);
}
int pop() {
return popAtStack(top);
}
int popAtStack(int index) {
if (index == -1 || index >= plates.size())
return -1;
auto &s = plates[index];
if (s.empty())
return -1;
int ans = s.back();
s.pop_back();
if (s.size() == capacity - 1)
non_full_stack.insert(index);
while (top >= 0 && plates[top].empty())
top--;
return ans;
}
};
/**
* 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);
*/