A stack is a pile where you add and remove only at the top. Design a stack that can also tell the smallest number inside it, and every operation must take constant time.
Write the class MinStack:
MinStack() creates an empty stack.void push(int val) puts val on the top.void pop() removes the top element.int top() returns the top element.int getMin() returns the smallest element in the stack.
Every method must run in O(1) time.
Examples
Example 1:
Input
["MinStack","push","push","push","getMin","pop","pop","getMin","top"]
[[],[6],[3],[9],[],[],[],[],[]]
Output
[null,null,null,null,3,null,null,6,6]
Explanation
Push 6, 3 and 9. The smallest is 3.
Pop removes 9, pop removes 3. Now only 6 is left.
The smallest is 6 and the top is 6.