#1172

Dinner Plate Stacks

master · 1895 · lc hard +32 · 33.5% accepted · 516 likes · top 11%

Description

Imagine a row of infinitely many stacks, each with an identical maximum capacity, numbered 0 onwards from left to right.

Build the DinnerPlates class:

- DinnerPlates(int capacity) sets up the structure with the given per-stack capacity.

- void push(int val) adds val to the leftmost stack that still has room.

- int pop() removes and returns the top element from the rightmost non-empty stack, or -1 if all stacks are empty.

- int popAtStack(int index) removes and returns the top element from the stack at position index, or -1 if that stack 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]

Example 2:

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.

Code

class DinnerPlates:

    def __init__(self, capacity: int):
        

    def push(self, val: int) -> None:
        

    def pop(self) -> int:
        

    def popAtStack(self, index: int) -> int:
        


# Your DinnerPlates object will be instantiated and called as such:
# obj = DinnerPlates(capacity)
# obj.push(val)
# param_2 = obj.pop()
# param_3 = obj.popAtStack(index)

class DinnerPlates:

    def __init__(self, capacity: int):
        

    def push(self, val: int) -> None:
        

    def pop(self) -> int:
        

    def popAtStack(self, index: int) -> int:
        


# Your DinnerPlates object will be instantiated and called as such:
# obj = DinnerPlates(capacity)
# obj.push(val)
# param_2 = obj.pop()
# param_3 = obj.popAtStack(index)