题目大意：
餐盘栈
我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 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 次调用。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1172
解题思路分析：
这道题的难点在于 popAtStack 这个方法，该方法可以在指定位置删除（pop）一个数值。如果本题没有这个操作的话就会变得很简单。我们定义两个变量pushIndex和popIndex，分别代表当前可以插入的stack下标和可以删除的stack下标，初始值都为0。因为是按顺序从左至右填满的每个Stack，因此，除了最后一个正在操作的stack之外，其他的都是填满的状态。
push操作时，可以向下标为pushIndex的stack中插入一个数字，插入后，当前stack一定存在了至少一个元素，因此 popIndex 可以更新为当前stack的下标。如果插入操作后，导致当前stack已满，pushIndex需要加一，向右移动到下一位，但popIndex保持不变（下一位的stack还没有元素）。
pop操作时，可以从下标为 popIndex 处删除一个元素。删除后，当前stack的存储量一定没有达到上限，pushIndex可以移动到当前stack的下标。如果删除操作后当前stack的元素个数为0， popIndex需要减一，向左移动到前一位，但 pushIndex 保持不变（当前stack为0，可以插入）
不过，本题加入了 popAtStack 方法之后，问题就变得稍微复杂一些。如果我们从已填满的一堆stack中删除了某个stack的元素，这时，index最小的非满Stack就不一定会出现在当前的操作位置了，所以要如何使用 pushIndex 和 popIndex 两个变量来管理插入和删除的位置呢？
其实问题也不难解决，总结一下，无非以下几种情况。
- pop操作。该操作一定会发生在最右边的非空Index。pop后，如果当前stack的元素个数变为0，说明，当前index上的stack已经无法再继续pop，我们需要从当前位置向左循环，找到第一个非空stack的下标，并将 popIndex 更新为该下标，以便下次pop操作时使用。另外，随着 popIndex 的改变，pushIndex 也需要做出相应的调整，变更过的 popIndex 应该代表了：当前popIndex的stack为非空（也可能已满），并且它右边的所有Stack都是空的，因此，如果此时 pushIndex 大于 popIndex 的话， pushIndex 应该调整到 popIndex 的位置，不过注意一下，如果 popIndex 位置的stack已满，代表其无法再插入数据， pushIndex 应该变为 popIndex + 1。
- popAtStack 操作。当传入的index大于 popIndex时，由于 popIndex 之后的stack都为空，可以直接返回-1。当传入的index等于 popIndex 时，相当于执行了pop操作，直接调用pop方法即可。上述之外的情况即是在中间的某个stack中删除元素，pop操作之后，该stack变为非空，如果该index小于 pushIndex，我们应该将 pushIndex 设置为当前值。
- push操作。该操作一定发生在最左边的非满stack，push操作后，如果该位置的stack已满，说明我们无法再继续向其插入数据，我们需要从当前位置向右循环找到第一个非满位置，并将 pushIndex 更新为该位置的下标，以便下次push操作时使用。同时，随着 pushIndex 的改变， popIndex 也应随之更新。此时， pushIndex 左边都是已满Stack，如果 popIndex 小于 pushIndex 的话， popIndex一定不是最右边的非空index，因此， popIndex 应该更新到 pushIndex 位置。不过，如果该位置为空， popIndex 应该为 pushIndex – 1。
实现代码：
int mCapacity;
int pushIndex;
int popIndex;
Stack<Integer>[] list = new Stack[100000];
public DinnerPlates(int capacity) {
mCapacity=capacity;
}
public void push(int val) {
Stack stack = list[pushIndex];
if(stack==null) stack=new Stack();
stack.push(val);
list[pushIndex]=stack;
if(stack.size()==mCapacity){
for(int i=pushIndex+1;i<list.length;i++){
if(list[i]==null||list[i].size()<mCapacity){
pushIndex=i;
break;
}
}
}
if(pushIndex>popIndex) popIndex=list[pushIndex]==null?pushIndex-1:pushIndex;
}
public int pop() {
if(list[popIndex].size()==0) return -1;
int res = list[popIndex].pop();
if(list[popIndex].size()==0){
for(int i=popIndex-1;i>=0;i--){
if(list[i].size()>0){
popIndex=i;
break;
}
}
}
if(popIndex<pushIndex) pushIndex=list[popIndex].size()==mCapacity?popIndex+1:popIndex;
return res;
}
public int popAtStack(int index) {
if(index==popIndex) return pop();
if(index>popIndex) return -1;
if(list[index].size()==0) return -1;
if(index<pushIndex) pushIndex=index;
return list[index].pop();
}本题解法执行时间为76ms。
Runtime: 76 ms, faster than 96.94% of Java online submissions for Dinner Plate Stacks.
Memory Usage: 138 MB, less than 100.00% of Java online submissions for Dinner Plate Stacks.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1172-dinner-plate-stacks-解题思路分析/