Min Stack

Min Stack

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

Implement the MinStack class:

• MinStack(): Initializes the stack object.
• push(val): Pushes the element val onto the stack.
• pop(): Removes the element on the top of the stack.
• top(): Gets the top element of the stack.
• getMin(): Retrieves the minimum element in the stack.

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

Examples

Example 1:

Input:
  MinStack(), push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output:
  null, null, null, null, -3, null, 0, -2
Explanation:
  MinStack minStack = new MinStack();
  minStack.push(-2);   // stack: [-2]
  minStack.push(0);    // stack: [-2, 0]
  minStack.push(-3);   // stack: [-2, 0, -3]
  minStack.getMin();   // return -3
  minStack.pop();      // stack: [-2, 0]
  minStack.top();      // return 0
  minStack.getMin();   // return -2

Constraints

• -2^31 <= val <= 2^31 - 1
• Methods pop, top, and getMin will always be called on non-empty stacks.
• At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Expected Complexity

• Time: O(1) per operation
• Space: O(n)