1172. Dinner Plate Stacks
Description
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 stackscapacity
.void push(int val)
Pushes the given integerval
into the leftmost stack with a size less thancapacity
.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 indexindex
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 topush
,pop
, andpopAtStack
.
Solutions
Solution 1: Stack Array + Ordered Set
We define the following data structures or variables:
capacity
: The capacity of each stack;stacks
: Stack array, used to store all stacks, each with a maximum capacity ofcapacity
;not_full
: Ordered set, used to store the indices of all non-full stacks in the stack array.
For the push(val)
operation:
- We first check if
not_full
is empty. If it is, it means there are no non-full stacks, so we need to create a new stack and pushval
into it. At this point, we check if the capacitycapacity
is greater than $1$. If it is, we add the index of this stack tonot_full
. - If
not_full
is not empty, it means there are non-full stacks. We take out the smallest indexindex
fromnot_full
, and pushval
intostacks[index]
. At this point, if the capacity ofstacks[index]
equalscapacity
, we removeindex
fromnot_full
.
For the popAtStack(index)
operation:
- We first check if
index
is within the index range ofstacks
. If it is not, we directly return $-1$. Ifstacks[index]
is empty, we also directly return $-1$. - If
stacks[index]
is not empty, we pop the top elementval
fromstacks[index]
. Ifindex
equals the length ofstacks
minus $1$, it meansstacks[index]
is the last stack. If it is empty, we loop to remove the index of the last stack fromnot_full
, and remove the last stack from the stack arraystacks
, until the last stack is not empty, or the stack arraystacks
is empty. Otherwise, ifstacks[index]
is not the last stack, we addindex
tonot_full
. - Finally, return
val
.
For the pop()
operation:
- We directly call
popAtStack(stacks.length - 1)
.
The time complexity is $(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of operations.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
|