Sometimes a data structure needs to answer a question fast that a plain stack cannot: "what is the smallest element currently inside?" Scanning the whole stack costs O(n) each time. With a little extra bookkeeping per element, the answer can be kept ready at all times.
Implement a class MinStack that supports:
push(x)– pushxonto the stack.pop()– remove the top element.top()– return the top element.get_min()– return the smallest element currently in the stack.
Every method must run in O(1) time. pop, top and get_min are only called on a non-empty stack. The tests drive the class with run_ops and compare the list of return values (None for methods that return nothing).
Examples
Input: ops = ["MinStack", "push", "push", "push", "get_min", "pop", "top", "get_min"]
args = [[], [-2], [0], [-3], [], [], [], []]
Output: [None, None, None, None, -3, None, 0, -2]
Explanation: the minimum is -3 until it is popped, then the minimum is back to -2.
Constraints
- At most 100 operations per test
-10**4 <= x <= 10**4
Goals
- Design a class whose methods share state through self
- Keep auxiliary data alongside a stack so that a query answers in O(1)
- Reason about why recomputing min(stack) on every call is too slow