Min Stack

A stack hands its values back in the opposite order they arrived: the last value pushed is the first one popped. Design a stack that can also say, at any moment, which value is the smallest of all the values it holds, and do every operation in constant time.

Implement the class MinStack:

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

The input is a list of operations, applied in order to one new MinStack. The output lists what the top and getMin calls return, in order. The starter code spells these names the way your language does.

Example 1:

Input:
    push(-2)
    push(0)
    push(-3)
    getMin()
    pop()
    top()
    getMin()
Output: -3 0 -2
Explanation:
After the three pushes the stack holds -2, 0 and -3, with -3 on top, so the smallest value is -3.
pop() removes -3. Now 0 is on top, and the smallest value is -2 again: when the minimum leaves,
the minimum from before it arrived comes back.

Example 2:

Input:
    push(5)
    push(5)
    push(7)
    getMin()
    pop()
    pop()
    getMin()
    top()
Output: 5 5 5
Explanation: 5 is pushed twice. The two pops remove 7 and one of the 5s, but the other 5 is still in the stack, so the smallest value is still 5.

Example 3:

Input:
    push(3)
    top()
    getMin()
    push(1)
    push(2)
    top()
    getMin()
    pop()
    pop()
    getMin()
Output: 3 3 2 1 3
Explanation: The value on top (2) and the smallest value (1) can be different values. Once 2 and 1 are popped, only 3 is left, and it is the smallest again.

Constraints:

• -231 <= val <= 231 - 1
• pop, top and getMin are only called when the stack is not empty.
• At most 2 * 105 calls in total are made to push, pop, top and getMin.