X

LEETCODE 1172. Dinner Plate Stacks 解题思路分析

题目大意:

餐盘栈

我们把无限数量 ∞ 的栈排成一行,按从左到右的次序从 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)一个数值。如果本题没有这个操作的话就会变得很简单。我们定义两个变量pushIndexpopIndex,分别代表当前可以插入的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就不一定会出现在当前的操作位置了,所以要如何使用 pushIndexpopIndex 两个变量来管理插入和删除的位置呢?

其实问题也不难解决,总结一下,无非以下几种情况。

  1. 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。
  2. popAtStack 操作。当传入的index大于 popIndex时,由于 popIndex 之后的stack都为空,可以直接返回-1。当传入的index等于 popIndex 时,相当于执行了pop操作,直接调用pop方法即可。上述之外的情况即是在中间的某个stack中删除元素,pop操作之后,该stack变为非空,如果该index小于 pushIndex,我们应该将 pushIndex 设置为当前值。
  3. 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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1172-dinner-plate-stacks-解题思路分析/
Categories: leetcode
kwantong: