441. Minimum-Aware Stack
A warehouse robot piles crates on top of each other, and every crate carries an integer rating printed on its side. The foreman keeps asking which crate in the pile currently has the lowest rating, and the robot is not allowed to unstack anything or rescan the pile to answer.
Implement the class MinAwareStack with a constructor that takes no arguments. push(value) places a crate with that rating on top, pop() removes the top crate, top() returns the rating of the top crate and getMin() returns the lowest rating among all crates currently in the pile. Every method must run in constant time. pop, top and getMin are only called while the pile is non-empty.
Example 1
- Input:
- operations = ["MinAwareStack","push","push","push","getMin","pop","top","getMin"]arguments = [[],[14],[9],[11],[],[],[],[]]
- Output:
- [null,null,null,null,9,null,9,9]
- Explanation:
After pushing 14, 9 and 11 the lowest rating is 9. Popping removes 11, so the top becomes 9 and the lowest is still 9.
Example 2
- Input:
- operations = ["MinAwareStack","push","push","pop","getMin","push","getMin","top"]arguments = [[],[6],[3],[],[],[8],[],[]]
- Output:
- [null,null,null,null,6,null,6,8]
- Explanation:
The 3 is removed again, so the lowest rating goes back to 6. Pushing 8 does not change it, and the top is 8.
Constraints
-231 ≤ value ≤ 231 - 1
At most 3 * 104 calls in totalpop, top and getMin are never called on an empty stack.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) per operation
- Space
- O(n)