Min Stack

Q: ¿Cómo se obtiene el mínimo de una pila en tiempo O(1)?

Registra el mínimo al insertar. Una pila solo cambia en la parte superior, así que el mínimo de los valores por debajo de cualquier altura no puede cambiar mientras esa altura esté ocupada. Mantén una segunda pila con el mínimo en cada altura, o solo cada nuevo mínimo, y getMin se convierte en una lectura de su parte superior.

Q: ¿Por qué insertar el valor en la pila de mínimos cuando es igual al mínimo actual?

Porque el valor mínimo puede estar en la pila más de una vez. Si registras solo valores estrictamente menores, dos copias de -2 comparten una entrada en mins . La primera extracción de -2 elimina esa entrada, y getMin entonces devuelve el mínimo anterior aunque el segundo -2 siga ahí. Registrar los valores iguales da a cada copia su propia entrada.

Q: ¿Se puede implementar Min Stack con espacio adicional O(1)?

Sí, con una pila y una variable min . Cuando apilas un x por debajo del mínimo actual, guarda 2x - min en su lugar y establece min = x ; el número almacenado es entonces menor que min , lo que lo marca. Cuando se desapila un número marcado, el mínimo anterior es 2 * min - stored . La aritmética desborda los enteros de 32 bits cerca de los límites, así que se necesitan valores de 64 bits, y la lógica de los signos es propensa a errores; a la mayoría de los entrevistadores les basta con la versión de dos pilas.

Q: ¿Cuál es la complejidad temporal y espacial de Min Stack?

Cada operación es O(1): push, pop, top y getMin leen o cambian solo la cima de una o dos pilas. El espacio es O(n) para n valores almacenados. Almacenar el mínimo junto a cada valor siempre usa 2n posiciones; almacenar solo los nuevos mínimos usa entre n + 1 y 2n.

MedioPila

+10

Diseña una pila que, además de las operaciones habituales push, pop y top, pueda indicar el valor más pequeño que contiene con getMin. Cada una de las cuatro operaciones debe ejecutarse en tiempo O(1).

Recibes las operaciones en orden como ops, y args[i] contiene el valor para una operación push y 0 para cualquier otra operación. Ejecútalas en una sola pila que empieza vacía y devuelve una cadena por operación: "null" para push y pop, y el número como texto para top y getMin.

Función

minStackOps(ops: string-array, args: integer-array) → string-array

opsstring-array: las operaciones, en el orden en que se ejecutan
argsinteger-array: el valor de cada operación push, 0 para todas las demás operaciones
Devuelvestring-array: una respuesta por operación, como texto

Restricciones

1 ≤ ops.length ≤ 3000
args.length == ops.length
Cada ops[i] es push, pop, top o getMin.
-2³¹+1 ≤ args[i] ≤ 2³¹-1 para una operación de inserción, y args[i] == 0 para cualquier otra operación.
pop, top y getMin solo se llaman cuando la pila contiene al menos un valor.

Ejemplos

Entrada: ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
Salida: ["null", "null", "null", "1", "null", "1", "null", "4"]
Explicación: La pila contiene 4, 1 y 7 de abajo hacia arriba, así que el menor es 1. Sacar 7 deja 1 arriba. Sacar también 1 deja solo 4, así que el mínimo vuelve a ser 4.

Entrada: ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
Salida: ["null", "null", "null", "-2", "null", "-2", "null", "3"]
Explicación: El mínimo, -2, se apila dos veces. La primera extracción elimina una copia y la otra sigue ahí, así que getMin sigue siendo -2. Solo después de la segunda extracción el mínimo vuelve a ser 3.

+16 pruebas ocultas al enviar

Para ir más allá

¿Puedes crear una cola de primero en entrar, primero en salir que también informe de su mínimo en tiempo O(1) amortizado?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una pila básica ya realiza push, pop y top en O(1); la parte difícil es mantener un mínimo que sobreviva a las extracciones. La idea clave es que una pila solo cambia en la parte superior: mientras un valor permanezca a cierta altura, nada por debajo puede cambiar, así que el mínimo de todos los elementos hasta esa altura es fijo. Anota ese mínimo cuando insertes un elemento y una extracción restaurará el anterior sin costo. Los enfoques difieren en qué anotan.

Recorre la pila en cada getMin

Intuición

Usa una pila ordinaria para push, pop y top, y responde a getMin observando todos los valores que contiene y conservando el menor. Esto siempre es correcto, porque comprueba el contenido real en el momento de la llamada.

Incumple el requisito O(1). Una llamada a getMin en una pila de n valores lee los n valores. La prueba oculta que apila 1,500 valores y llama a getMin después de cada inserción lee aproximadamente 1,500 × 1,500 / 2, más de un millón de valores, mientras que los otros enfoques leen uno por llamada. Un sistema que ejecutara 10^5 operaciones de este tipo leería miles de millones de valores.

Guardar en caché un único mínimo no lo soluciona. Una variable que contiene el menor valor sirve para las inserciones, pero una vez que ese valor se extrae de la pila, no puedes saber cuál es el siguiente menor sin volver a recorrerla.

Algoritmo

Almacena los valores en una lista utilizada como pila.
Para push x, añade x; para pop, elimina el último valor; para top, léelo.
Para getMin, recorre todos los valores almacenados y devuelve el más pequeño.
Registra cada respuesta como texto y devuelve la lista.

class MinStack:
    def __init__(self):
        self.values = []

    def push(self, x):
        self.values.append(x)

    def pop(self):
        self.values.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        # Look at every stored value: O(n).
        smallest = self.values[0]
        for v in self.values:
            if v < smallest:
                smallest = v
        return smallest

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Almacena el mínimo junto a cada valor

Intuición

Mientras un valor se encuentre a la altura i de la pila, los valores que están debajo no pueden cambiar, así que el menor de los i valores inferiores permanece fijo mientras ese valor esté ahí. Guarda ese número junto a cada valor: una segunda pila mins donde mins[i] es el menor de values[0..i].

Al insertar un elemento, la nueva entrada de mins es el menor entre x y la entrada que está debajo. Al extraer un elemento, quita la cima de ambas pilas; la cima de mins vuelve a ser el mínimo de lo que queda. getMin lee la cima de mins.

En el primer ejemplo, las inserciones 4, 1 y 7 almacenan mínimos de 4, 1 y 1. Al extraer 7, queda 1 en la cima de mins, y al extraer 1, queda 4. Cada operación solo toca las cimas de dos pilas, así que cada una es O(1). El coste es un segundo número por cada valor.

Algoritmo

Mantén dos pilas de la misma altura, values y mins.
Para push x, agrega x a values y agrega el menor entre x y la cima de mins a mins (x mismo si mins está vacío).
Para pop, desapila ambas pilas.
Para top, lee la cima de values; para getMin, lee la cima de mins.
Registra cada respuesta como texto y devuelve la lista.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # mins[i] is the smallest of values[0..i]

    def push(self, x):
        self.values.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def pop(self):
        self.values.pop()
        self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Una pila de mínimos que solo crece cuando aparece un nuevo mínimo

Intuición

En el segundo enfoque, mins suele repetir valores: inserta 1 y después 7, 8 y 9, y mins contiene 1, 1, 1, 1. Una entrada repetida no aporta nada nuevo. Así que registra un valor en mins solo cuando se convierte en el mínimo, y elimínalo cuando ese mismo valor salga de values.

Al insertar, añade x a mins si mins está vacío o si x es menor o igual que su cima. Al extraer, si el valor que sale de values es igual a la cima de mins, extrae también de mins. La cima de mins siempre es el mínimo actual: todo valor insertado después de él es mayor, o bien era menor o igual que él, también se registró y se extrajo desde entonces.

La comparación debe ser <=, no <. En el segundo ejemplo se inserta -2 dos veces. Con <, solo se registra la primera copia; la primera extracción la elimina de mins, y getMin devuelve 3 mientras todavía queda un -2 en la pila. Con <=, cada copia obtiene su propia entrada.

Las cuatro operaciones siguen siendo O(1). Cuando los valores llegan de mayor a menor, mins alcanza la misma altura que values; cuando el mínimo cambia rara vez, se mantiene corta.

Algoritmo

Mantén una pila values y una pila mins.
Para push x, inserta x en values. Si mins está vacía o x es menor o igual que su elemento superior, inserta también x en mins.
Para pop, extrae un elemento de values. Si el valor extraído es igual al elemento superior de mins, extrae también un elemento de mins.
Para top, lee el elemento superior de values; para getMin, lee el elemento superior de mins.
Registra cada respuesta como texto y devuelve la lista.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # each value that was a minimum when pushed; the top is the current minimum

    def push(self, x):
        self.values.append(x)
        # <= keeps one copy per equal minimum, so popping one leaves the others.
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)

    def pop(self):
        if self.values.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Errores comunes y casos límite

Los errores aquí tienen que ver con las copias del mínimo y con lo que elimina una operación de extracción.

Registrar un nuevo mínimo solo cuando x es estrictamente menor. Entonces falta una segunda copia del mínimo en mins, y al extraer la primera copia se pierde el mínimo aunque la segunda siga en la pila. El segundo ejemplo detecta esto.
Guardar el mínimo en una sola variable. Esto permite gestionar las inserciones, pero después de extraer el mínimo, la variable queda desactualizada, y encontrar el siguiente valor más pequeño requiere recorrer la pila.
Comparar enteros encapsulados por referencia. En Java, Integer == Integer comprueba si ambos son el mismo objeto. Esto resulta ser cierto para los valores de -128 a 127, que Java almacena en caché, y falla con la mayoría de los valores más grandes, por lo que la comprobación al extraer falla solo con valores grandes. Primero convierte a int, como hace el código Java.
Extraer de mins en cada operación de extracción en el tercer enfoque. Solo se reduce cuando el valor eliminado está en la cima; en el segundo enfoque, las dos pilas siempre avanzan juntas.
Devolver un número para pop. En este formato, pop devuelve "null", al igual que push.

Preguntas frecuentes4

¿Cómo se obtiene el mínimo de una pila en tiempo O(1)?

Registra el mínimo al insertar. Una pila solo cambia en la parte superior, así que el mínimo de los valores por debajo de cualquier altura no puede cambiar mientras esa altura esté ocupada. Mantén una segunda pila con el mínimo en cada altura, o solo cada nuevo mínimo, y getMin se convierte en una lectura de su parte superior.

¿Por qué insertar el valor en la pila de mínimos cuando es igual al mínimo actual?

Porque el valor mínimo puede estar en la pila más de una vez. Si registras solo valores estrictamente menores, dos copias de -2 comparten una entrada en mins. La primera extracción de -2 elimina esa entrada, y getMin entonces devuelve el mínimo anterior aunque el segundo -2 siga ahí. Registrar los valores iguales da a cada copia su propia entrada.

¿Se puede implementar Min Stack con espacio adicional O(1)?

Sí, con una pila y una variable min. Cuando apilas un x por debajo del mínimo actual, guarda 2x - min en su lugar y establece min = x; el número almacenado es entonces menor que min, lo que lo marca. Cuando se desapila un número marcado, el mínimo anterior es 2 * min - stored. La aritmética desborda los enteros de 32 bits cerca de los límites, así que se necesitan valores de 64 bits, y la lógica de los signos es propensa a errores; a la mayoría de los entrevistadores les basta con la versión de dos pilas.

¿Cuál es la complejidad temporal y espacial de Min Stack?

Cada operación es O(1): push, pop, top y getMin leen o cambian solo la cima de una o dos pilas. El espacio es O(n) para n valores almacenados. Almacenar el mínimo junto a cada valor siempre usa 2n posiciones; almacenar solo los nuevos mínimos usa entre n + 1 y 2n.

Python

def minStackOps(ops, args):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]
args = [4, 1, 7, 0, 0, 0, 0, 0]

Esperado

["null", "null", "null", "1", "null", "1", "null", "4"]

Min Stack

Función

Restricciones

Ejemplos

Pistas

Solución

Recorre la pila en cada getMin

Almacena el mínimo junto a cada valor

Una pila de mínimos que solo crece cuando aparece un nuevo mínimo

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares