1172.Dinner Plate Stacks¶

1172.Dinner Plate Stacks¶

Tags: Hard Design

Links: https://leetcode.com/problems/dinner-plate-stacks/

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Example:

Input: 
["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],[],[],[],[],[]]
Output: 
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

Constraints:

1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
At most 200000 calls will be made to push, pop, and popAtStack.

class DinnerPlates {
    vector<stack<int>> v;
    int pos; //存储最后一个存储数据的栈的下标
    int cap; //栈的容量
    int firstNotFull; //存储第一个没有满的栈的下标
public:
    DinnerPlates(int capacity) {
        cap = capacity;
        pos = 0;
        firstNotFull = 0;
        v.resize(100000);
    }

    void push(int val) {
        //如果第一个没有满的栈恰好是最后一个栈
        if (firstNotFull == pos) {
            v[pos].push(val);
            //加入元素后可能栈满，需要修改firstNotFull
            if (v[pos].size() == cap) ++firstNotFull;
        }
        //firstNotFull > pos只可能是pos的栈存满
        else if (firstNotFull > pos) {
            v[firstNotFull].push(val);
            ++pos;
            if (v[pos].size() == cap) ++firstNotFull;
        }
        //第一个非空的栈是最后一个非空栈前面的栈
        else {
            v[firstNotFull].push(val);
            //根据当前栈是否存满，来更新firstNotFull
            while (v[firstNotFull].size() == cap) ++firstNotFull;
        }
    }

    int pop() {
        //如果所有的栈都是空的
        if (v[pos].empty() && pos == 0) return -1;

        int res = v[pos].top();
        v[pos].pop();
        //更新pos，始终让pos指向最后一个非空的栈的下标
        while (v[pos].empty() && pos > 0) --pos;
        //更新firstNotFull
        if (firstNotFull - pos > 1) firstNotFull = pos + 1;

        return res;
    }

    int popAtStack(int index) {
        //访问的是空栈
        if (index > pos || v[index].empty()) return -1;

        int res = v[index].top();
        //index == pos等价于pop()
        if (index == pos) pop();
        else { //只能是index < pos的情况
            v[index].pop();
            //index <= firstNotFull需要更新
            if (index < firstNotFull) {
                firstNotFull = index;
            }
        }

        return res;
    }
};

/**
 * 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);
 */

Runtime: 1456 ms, faster than 5.02% of C++ online submissions for Dinner Plate Stacks.
Memory Usage: 571.9 MB, less than 100.00% of C++ online submissions for Dinner Plate Stacks.

最初没看提示的时候的解答。从结果来看，属于擦边通过。

因为题目给出了数据范围，所以可以最开始就开一个数组，数组每个位置存储一个栈，用变量pos代表最后一个非空的栈，用变量firstNotFull代表第一个不满的栈，所以接下来的问题就是考虑什么时候需要更新这两个变量。

首先考虑push操作。firstNotFull和pos的关系决定了不同的处理：

firstNotFull == pos，说明最后一个栈是不满的，那么把数据加入最后一个栈。但是需要考虑加入数据后栈变满了，那么就可能需要更firstNotFull。
firstNotFull >pos，只可能是pos是满的。
firstNotFull < pos，那么肯定是把数据加入firstNotFull所在的栈，那么可能firstNotFull所在的栈存满了，于是更新firstNotFull

然后考虑pop操作：pop是从最后一个非空的栈开始删除元素，那么直接删除pos对应的栈顶的元素即可。但是删除操作可能带来pos和firstNotFull的更新。删除一个操作后可能导致pos对应的栈空了，那么就往前寻找非空的栈来更新pos。firstNotFull考虑其和pos在更新后的关系，如果pos <=firstNotFull，那么firstNotFull无需更新，但是如果是存在firstNotFull-pos > 1，那么只可能是一种情况，firstNotFull = pos + 1，也就是在删除开始之前，pos对应的栈是满的，但是删除之后空了，其实也就意味着容量是1。

最后考虑指定索引的删除操作。如果index == pos，那么和需要实现的类函数中的pop()是一样的。比较麻烦的是处理index < pos的情况，它影响的是firstNotFull。如果index >= firstNotFull，那么无影响，小于的情况意味着被删的index对应的栈空出了一个位置，那么只需要让firstNotFull更新为index即可。