Pila de mínimo en tiempo constante
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
Un solo número que guarde el mínimo falla en cuanto se hace pop de ese mínimo, porque el mínimo anterior ya se perdió. Hay que conservar el historial de alguna forma.
Fíjate en que el mínimo solo cambia al hacer push y pop, y cambia en orden de último en entrar, primero en salir, exactamente igual que la propia pila.
Junto a los valores, mantén una pila paralela cuyo tope siempre guarde el mínimo de todo lo que hay por debajo del nivel correspondiente. Al hacer push, guarda el menor entre el valor nuevo y el mínimo actual. Al hacer pop, descarta a la vez el tope de las dos pilas.
- 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
Solución
Una segunda pila refleja a la principal y guarda en cada nivel el mínimo de todo lo que hay en ese nivel o por debajo. Cada push registra el menor entre el valor entrante y el mínimo anterior, así que el tope de la pila espejo siempre es la respuesta. Cada pop descarta los dos topes juntos, lo que restaura automáticamente el mínimo anterior y maneja bien los mínimos duplicados. Cada operación es O(1) de tiempo, y el espacio es O(n) por la pila extra.
class MinStack:
def __init__(self): self.items, self.mins = [], [] # mins mirrors the running minimum
def push(self, x):
self.items.append(x)
# each level remembers the minimum of everything at or below it
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop() # both stacks always shrink together
return self.items.pop()
def top(self): return self.items[-1]
def minimum(self): return self.mins[-1]
s = MinStack()
for v in (5, 2, 7): s.push(v)
print(s.minimum(), s.top()) # -> 2 7
s.pop(); s.pop()
print(s.minimum(), s.top()) # -> 5 5¿Lo que te frena es la idea y no el código? Min Stack lo explica.