Problema
Un Stack<T> generic funciona para cualquier tipo. Aquí amplías la idea: una pila de enteros que también puede informar de su mínimo en tiempo constante.
Procesa las operaciones en orden:
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.
Implementa min_stack_operations(operations).
Entrada
operations: Las operaciones.
Salida
Devuelve las respuestas de las operaciones min, en orden.
Restricciones
1 ≤ número de operaciones ≤ 200,000
0 ≤ x ≤ 10^9
Ejemplos
Entrada:
operations = ["push 5", "push 3", "min", "pop", "min"]
Salida esperada:
expected = [3, 5]Entrada:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
Salida esperada:
std::vector<long long> expected = {3, 5};Entrada:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
Salida esperada:
long[] expected = new long[] {3, 5};Explicación
Con 5 y 3 en la pila, el mínimo es 3. Después de sacar 3, solo queda 5: [3, 5].
Entrada:
operations = ["min", "pop", "push 7", "min"]
Salida esperada:
expected = [-1, 7]Entrada:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
Salida esperada:
std::vector<long long> expected = {-1, 7};Entrada:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
Salida esperada:
long[] expected = new long[] {-1, 7};Explicación
La pila vacía devuelve -1 y el pop se ignora; luego el mínimo es 7: [-1, 7].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Junto a cada valor, guarda el mínimo de la pila en ese momento.
Pista 2
Así el mínimo actual es simplemente la cima de esa segunda pila.
Pista 3
Ignora pop con la pila vacía y responde -1 a min cuando esté vacía.
Complejidad esperada
tiempo O(número de operaciones), espacio extra O(número de operaciones)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.