Условие
A generic Stack<T> works for any type. Here you extend the idea: a stack of integers that can also report its minimum in constant time.
Process the operations in order:
push <x>: push x.pop: remove the top value (ignored when the stack is empty).min: report the smallest value currently in the stack, or -1 if it is empty.
Implement min_stack_operations(operations).
Input
operations: The operations.
Output
Return the answers of the min operations, in order.
Ограничения
1 ≤ number of operations ≤ 200,000
0 ≤ x ≤ 10^9
Примеры
Ввод:
operations = ["push 5", "push 3", "min", "pop", "min"]
Ожидаемый вывод:
expected = [3, 5]Ввод:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
Ожидаемый вывод:
std::vector<long long> expected = {3, 5};Ввод:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
Ожидаемый вывод:
long[] expected = new long[] {3, 5};Пояснение
With 5 and 3 on the stack the minimum is 3. After popping 3, only 5 is left: [3, 5].
Ввод:
operations = ["min", "pop", "push 7", "min"]
Ожидаемый вывод:
expected = [-1, 7]Ввод:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
Ожидаемый вывод:
std::vector<long long> expected = {-1, 7};Ввод:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
Ожидаемый вывод:
long[] expected = new long[] {-1, 7};Пояснение
The empty stack reports -1 and the pop is ignored; then the minimum is 7: [-1, 7].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Store, next to each value, the minimum of the stack at that point.
Подсказка 2
The current minimum is then simply the top of that second stack.
Подсказка 3
Ignore pop on an empty stack, and answer -1 for min when it is empty.
Ожидаемая сложность
O(number of operations) time, O(number of operations) extra space
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.