Min Stack
Medium · stack
A stack of integers starts empty and receives a list of operations. operations[i] is one of "push", "pop", "top" or "min", and values[i] is the number to push when the operation is "push" (it is 0 and should be ignored for every other operation).
"push"putsvalues[i]on top of the stack."pop"removes the top number."top"reads the top number without removing it."min"reads the smallest number currently on the stack, without removing anything.
Return a list with the answer to every "top" and "min" operation, in the order they appear. "pop", "top" and "min" are only ever used when the stack is not empty.
Examples
Example 1
Input: operations = ["push", "push", "min", "push", "min", "pop", "min", "top"], values = [4, 2, 0, 1, 0, 0, 0, 0]
Output: [2, 1, 2, 2]
After the first two pushes the stack is 4, 2 and its smallest is 2. After pushing 1 the smallest is 1. Popping the 1 brings the smallest back to 2, and the top is 2.
Example 2
Input: operations = ["push", "top", "push", "top", "pop", "top"], values = [7, 0, 9, 0, 0, 0]
Output: [7, 9, 7]
Example 3
Input: operations = ["push", "push", "pop", "min"], values = [5, 5, 0, 0]
Output: [5]
Equal numbers are both kept, so the stack is still 5 after the pop.
Constraints
- 1 <= len(operations) <= 10^4
- len(values) == len(operations)
- operations[i] is one of push, pop, top, min
- -2^31 <= values[i] <= 2^31 - 1
- pop, top and min are only used on a non-empty stack.