Min Stack
Design a stack that supports push, pop, and top like a normal stack, and also returns the smallest value it currently holds through a getMin operation. Every operation must run in O(1) time.
Implement the MinStack class with push(val) to add a value, pop() to remove the value on top, top() to read the value on top, and getMin() to read the minimum value in the stack.
The input is a list of operations. Each top and getMin prints the value it reads. A getMin is only queried when the stack is non-empty.
Input & Output
Input
operations — a list of operations, each one of push val, pop, top, or getMin
Output
the values printed by the top and getMin operations, in order