[LeetCode] 1172. Dinner Plate Stacks

[grandyang]

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 capacity.
• void push(int val) Pushes the given integer val into the leftmost stack with a 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 the stacks are empty.
• int popAtStack(int index) Returns the value at the top of the stack with the given index index and removes it from that stack or returns -1 if the stack with that given index is empty.

Example 1:

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 <= 2 * 104
• 1 <= val <= 2 * 104
• 0 <= index <= 105
• At most 2 * 105 calls will be made to push, pop, and popAtStack.

这道题定义了一种餐盘栈的数据结构，说是有很多个栈从左到右排成一排，每个栈有个最大容量 capacity，现在定义了三种操作，push 是将给定的数字 val 压入左起第一个未满的栈，pop 是移除并返回右起第一个非空的栈顶元素，不存在则返回 -1。popAtStack 是移除并返回给定 index 位置的栈顶元素，不存在则返回 -1。题目的例子给了详细的解释，不难理解题意，但一定要将屏幕拉宽，让栈中的数字对齐，不然会产生疑惑，至少博主第一次看的时候产生了。既然是要有很多栈，那么可以把这些栈都放到一个数组中，栈本身可以用个 vector 来代替，所以这里就用个二维数组 stacks 就可以了。然后再来想这道题的难点是什么，对于 push 函数来说，要找到左起第一个未满的栈，怎么才能知道哪个栈未满呢，一个一个去遍历吗？未免太不高效了，最好这里能记录所有未满的栈的位置，所以这里用个 TreeSet 来记录，可以利用其自动排序的特点，则第一个元素一定是左起第一个栈，最后一个元素一定是右起第一个栈。首先来判定 openSt 是否为空，若为空，便是当前没有未满的栈，则需要新增一个空栈，将该新栈位置加入 openSt 中，并且 stacks 扩大一位。然后取出 openSt 的首元素，即为左起第一个未满的栈，将 val 加入其中。然后需要判断加入后该栈是否已经满了，是的话则从 openSt 中移除该位置。对于 pop 来说，这里可以直接调用 popAtStack 函数，传入 stacks 的末尾位置。对于 popAtStack 来说，首先要判断给定的 index 参数是否越界，若越界或者对应的栈为空，则直接返回 -1。否则取出对应的栈顶元素，然后将当前位置 index 加入 openSt，因为此时栈未满了。接下来有个很重要的操作，从右起移除所有为空的栈，不然下次调用 pop 后可能无法返回正确元素。用一个 while 循环，若右起第一个栈为空，则移除，同时将 openSt 中对应的位置也要移除，参见代码如下：

class DinnerPlates {
public:
    DinnerPlates(int capacity) {
        cap = capacity;
    }
    
    void push(int val) {
        if (openSt.empty()) {
            openSt.insert(stacks.size());
            stacks.resize(stacks.size() + 1);
        }
        stacks[*openSt.begin()].push_back(val);
        if (stacks[*openSt.begin()].size() == cap) {
            openSt.erase(openSt.begin());
        }
    }
    
    int pop() {
        return popAtStack((int)stacks.size() - 1);
    }
    
    int popAtStack(int index) {
        if (index < 0 || index >= stacks.size() || stacks[index].empty()) {
            return -1;
        }
        int res = stacks[index].back();
        stacks[index].pop_back();
        openSt.insert(index);
        while (!stacks.empty() && stacks.back().empty()) {
            stacks.pop_back();
            openSt.erase(*openSt.rbegin());
        }
        return res;
    }
    
private:
    vector<vector<int>> stacks;
    set<int> openSt;
    int cap;
};

Github 同步地址:

#1172

参考资料：

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

https://leetcode.com/problems/dinner-plate-stacks/discuss/366331/C%2B%2BPython-Two-Solutions

https://leetcode.com/problems/dinner-plate-stacks/discuss/367554/Java-O(logn)-Operations-Using-List-and-TreeSet

LeetCode All in One 题目讲解汇总(持续更新中...)