# 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 `push``pop`, and `popAtStack`.

``````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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation