1172. 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 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 pushpop, 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation