Saltar al contenido

Pila de mínimo en tiempo constante

Fácil#stack#auxiliary-stack~20 min

La misión

Problema

Diseña una pila (stack) que permita hacer push de un valor, hacer pop del valor del tope, leer el valor del tope e informar el valor más pequeño que guarda en ese momento. Cada una de esas operaciones debe ejecutarse en tiempo constante, así que recorrer el contenido para encontrar el mínimo no es aceptable. Puedes suponer que el mínimo solo se pide mientras la pila no está vacía.

Ejemplos

Operations: push 5, push 2, push 7
minimum -> 2, top -> 7
Operations: pop, pop        (starting from the stack above)
minimum -> 5, top -> 5
Por qué: hacer pop del 2 debe restaurar el mínimo anterior
Operations: push 3, push 3, pop
minimum -> 3
Por qué: caso límite: los mínimos duplicados deben sobrevivir a un pop

Pistas

0 / 3

Tiempo objetivo
O(1)
Espacio objetivo
O(n)

Restricciones

  • every operation runs in O(1) time
  • minimum is only requested on a non-empty stack

¿Lo que te frena es la idea y no el código? Min Stack lo explica.

Python 3Ctrl+Enter ejecuta