Min Stack

Build a stack of integers that can also tell you, at any moment, the smallest value it currently holds. Implement the MinStack class:

• MinStack() creates an empty stack.
• push(value) puts value on top of the stack.
• pop() removes the value on top.
• top() returns the value on top without removing it.
• getMin() returns the smallest value anywhere in the stack.

Every method must run in O(1) time. Looking through the whole stack inside getMin is too slow at these sizes. Note that a pop can remove the current minimum, and getMin must then report the next smallest value that is still there.

Each example lists the calls in order, then the arguments of each call, then what each call returns: null for the constructor and for push and pop, which return nothing.

Example 1

Input:
["MinStack", "push", "push", "getMin", "push", "getMin", "top", "pop", "getMin", "top"]
[[], [6], [8], [], [2], [], [], [], [], []]
Output: [null, null, null, 6, null, 2, 2, null, 6, 8]

With 6 and 8 on the stack the minimum is 6. Pushing 2 makes 2 both the top and the minimum. Popping it leaves [6, 8] again, so the minimum goes back to 6 and the top is 8.

Example 2

Input:
["MinStack", "push", "push", "push", "pop", "getMin", "pop", "getMin"]
[[], [5], [3], [3], [], [], [], []]
Output: [null, null, null, null, null, 3, null, 5]

The minimum 3 was pushed twice. Popping one copy leaves the other, so the minimum is still 3. Only after the second pop does it rise to 5.

Example 3

Input:
["MinStack", "push", "push", "getMin", "pop", "getMin", "top"]
[[], [2147483647], [-2147483648], [], [], [], []]
Output: [null, null, null, -2147483648, null, 2147483647, 2147483647]

Values span the full 32-bit range. Once the smallest one is popped, the only value left is both the minimum and the top.

Constraints

• -2³¹ <= value <= 2³¹ - 1
• pop, top and getMin are only called when the stack is not empty.
• At most 3 * 10⁴ calls are made in total to push, pop, top and getMin.