Min Stack
MediumStack
Design a class MinStack that behaves like a normal last-in, first-out stack of integers and can also report the smallest value currently in it.
Implement:
MinStack()creates an empty stack.push(val)puts the integervalon top of the stack.pop()removes the top element. It returns nothing.top()returns the top element without removing it.getMin()returns the smallest element currently in the stack, without removing it.
Every method must run in O(1) time. The same value may be pushed more than once, and each copy counts separately.
In the examples, the output list has one entry per call: null for the constructor, push, and pop, and the returned value for top and getMin.
Example 1
- Input:
- MinStack(); push(3); push(1); getMin(); pop(); top(); getMin()
- Output:
- [null,null,null,1,null,3,3]
- Explanation
- The first
getMinsees 3 and 1 and returns 1. After the pop only 3 is left, so bothtopandgetMinreturn 3.
Example 2
- Input:
- MinStack(); push(2); push(0); push(0); getMin(); pop(); getMin(); pop(); top(); getMin()
- Output:
- [null,null,null,null,0,null,0,null,2,2]
- Explanation
- Both copies of 0 are tracked separately, so after one pop the minimum is still 0. Only after the second pop does it go back to 2.
Example 3
- Input:
- MinStack(); push(-1); push(4); push(-6); top(); getMin(); pop(); getMin(); top()
- Output:
- [null,null,null,null,-6,-6,null,-1,4]
- Explanation
- -6 is the minimum while it is on the stack. Popping it restores the previous minimum of -1, while the top becomes 4.
Constraints
- -231 ≤
val≤ 231 - 1 pop,top, andgetMinare only called when the stack is non-empty- At most 3 * 104 calls are made in total