Rolling Min Price Stack
A pricing engine keeps a stack of quoted prices and must answer 'what is the lowest price currently on the stack?' instantly after every push and pop. Design a stack with O(1) minimum lookup.
Problem
Design a stack supporting push(x), pop(), top(), and getMin() — the minimum element currently on the stack — each in O(1) time. Process a sequence of operations and return the outputs of the query operations in order.
Input
A list of operations, each one of: "push v", "pop", "top", "getMin" (1 ≤ count ≤ 10^5).
Output
A list of integers — the result of each top/getMin query, in order.
Constraints
- All four operations run in O(1)
- pop/top/getMin are only called on a non-empty stack
- Values fit in a 32-bit int
Examples
Example 1
Input
ops = ["push -2", "push 0", "push -3", "getMin", "pop", "top", "getMin"]
Output
[-3, 0, -2]
After pushing -2,0,-3 the min is -3; pop removes -3; top is 0; min is now -2.
Example 2
Input
ops = ["push 5", "getMin", "top"]
Output
[5, 5]
A single element is both the top and the minimum.