Min Stack

Medium~20 min

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() — Initialize the stack object.
push(val) — Push the integer val onto the stack.
pop() — Remove the element on the top of the stack.
top() — Return the top element of the stack.
getMin() — Return the minimum element currently in the stack.

You must implement a solution with O(1) time complexity for each function.

Examples

Example 1

Input:

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[], [-2], [0], [-3], [], [], [], []]

Output: [null,null,null,null,-3,null,0,-2]

Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints

-10000 <= val <= 10000
Methods pop, top, and getMin will always be called on non-empty stacks
At most 10000 calls will be made to push, pop, top, and getMin

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run