Remove K Digits

Q: ¿Cuál es la complejidad temporal de Remove K Digits?

Con una pila monótona, se ejecuta en tiempo O(n) para n dígitos: cada dígito se apila una vez y cada extracción consume una de las k eliminaciones. La pila contiene hasta n dígitos, así que el espacio adicional es O(n) . Volver a recorrer desde la izquierda por cada eliminación cuesta O(n·k) .

MedioPila monótona Voraz

+10

Recibes un número no negativo escrito como una cadena de dígitos, num, y un entero k. Elimina exactamente k dígitos y conserva el resto en su orden original, de modo que el número resultante sea lo más pequeño posible.

Devuélvelo como una cadena sin ceros iniciales. Si no queda nada, o solo quedan ceros, devuelve "0".

Función

removeKdigits(num: string, k: integer) → string

numstring: el número, escrito como una cadena de dígitos
kinteger: cuántos dígitos eliminar
Devuelvestring: el número más pequeño que puedes dejar, como cadena sin ceros iniciales

Restricciones

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num contiene solo los dígitos del 0 al 9.
num no tiene ceros iniciales, excepto cuando es el propio número cero, "0".

Ejemplos

Entrada: num = "4325043"k = 3
Salida: "2043"
Explicación: Al quitar el 4 y el primer 3, el 2 queda al principio. El 0 no puede ir primero: hay cuatro dígitos delante y tienes tres eliminaciones. La última eliminación quita el 5, que está antes de un 0 más pequeño.

Entrada: num = "30200"k = 1
Salida: "200"
Explicación: Quitar el 3 deja 0200, y sin el cero inicial es 200. Cualquier otra eliminación mantiene el 3 delante y deja un número de cuatro dígitos, como 3000.

Entrada: num = "52"k = 2
Salida: "0"
Explicación: Se eliminan ambos dígitos, así que no queda nada y la respuesta es "0".

Para ir más allá

¿Cómo cambiarías la solución para eliminar k dígitos y dejar el número más grande?

Pistas

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

0 de 3 abiertas

Solución

Los dígitos más a la izquierda tienen más peso, así que debe eliminarse el primer dígito que sea mayor que su vecino de la derecha. Una pila con los dígitos que conservas aplica esa regla a toda la cadena en una sola pasada. Las eliminaciones que queden se hacen desde el final, y los ceros iniciales se eliminan al final.

Elimina un dígito a la vez

Correcto, pero no termina con las pruebas más grandes

Intuición

Elimina un dígito a la vez: encuentra la primera posición i donde num[i] > num[i+1] y elimina num[i], o elimina el último dígito si los dígitos nunca disminuyen. Repite k veces.

Todas las respuestas conservan n-k dígitos, así que la primera posición donde dos respuestas difieren determina cuál es menor. Hasta i, los dígitos nunca disminuyen, por lo que eliminar un dígito anterior hace que ocupe su lugar uno al menos igual de grande; eliminar uno posterior deja en su sitio el num[i] grande. Eliminar num[i] reduce la primera posición que se puede reducir.

Cada eliminación vuelve a recorrer los dígitos desde la izquierda y desplaza los dígitos que la siguen, así que el trabajo es O(n·k). Con 40,000 unos y k = 25,000, los recorridos leen unos 6.9 × 10^8 dígitos.

Algoritmo

Copia los dígitos en una lista de la que puedas borrar elementos.
Repite k veces: recorre desde la izquierda hasta el primer dígito mayor que el siguiente, o hasta el último dígito, y bórralo.
Elimina los ceros iniciales y devuelve "0" si no queda nada.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

Pila monótona de dígitos conservados

Intuición

Después de que la versión lenta elimina num[i], los dígitos anteriores a i siguen sin bajar nunca, así que la siguiente eliminación solo puede empezar en el dígito anterior al hueco. Una pila guarda ese prefijo: los dígitos conservados, que nunca decrecen de abajo hacia arriba. Cuando un dígito nuevo es menor que el de arriba, el de arriba es mayor que su vecino de la derecha, el dígito que eliminaría la versión lenta. Sácalo de la pila, consume una eliminación y sigue sacando mientras el nuevo dígito de arriba siga siendo mayor.

Con 4325043 y k = 3, el 3 saca el 4, el 2 saca el 3 y el 0 saca el 5. El 4 y el 3 se apilan a medida que aparecen, dando 2043.

Cada dígito se apila una vez y cada extracción consume una de las k eliminaciones, así que el recorrido es O(n).

Algoritmo

Crea una pila vacía de dígitos.
Para cada dígito de num: mientras queden eliminaciones y el elemento superior de la pila sea mayor que el dígito, extrae el elemento superior y consume una eliminación. Después, inserta el dígito.
Si quedan eliminaciones después del bucle, elimina esa cantidad de dígitos de la parte superior de la pila.
Lee la pila de abajo hacia arriba, omite los ceros iniciales y devuelve el resto, o "0" si no queda nada.

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

Errores comunes y casos límite

Eliminar cuando la cima es igual al nuevo dígito. Con 112 y k = 1, queda 12; la respuesta correcta es 11.
Olvidar las eliminaciones que quedan después del bucle o hacerlas desde el principio. La pila nunca disminuye, así que sus últimos dígitos son: 123456789 con k = 3 da 123456.
Contar los ceros eliminados como eliminaciones. En 100200 con k = 1, el 1 es la única eliminación; los ceros del principio se eliminan gratis y la respuesta es 200.
Devolver una cadena vacía. Con 10 y k = 1, solo queda un cero, así que la respuesta es "0".
Convertir num en un entero. Puede tener 4 × 10^4 dígitos, muy por encima de lo que admite cualquier tipo entero, así que compara los dígitos como caracteres.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Remove K Digits?

Con una pila monótona, se ejecuta en tiempo O(n) para n dígitos: cada dígito se apila una vez y cada extracción consume una de las k eliminaciones. La pila contiene hasta n dígitos, así que el espacio adicional es O(n). Volver a recorrer desde la izquierda por cada eliminación cuesta O(n·k).

¿Cómo se manejan los ceros iniciales en Remove K Digits?

Elimina primero los dígitos y quita los ceros solo al final. Un cero al principio no cambia el valor, así que no cuesta ninguna eliminación: 10200 con k = 1 se convierte en 0200 y después en 200. Si al quitar los ceros no queda nada, devuelve "0".

¿Se puede resolver «Eliminar K dígitos» usando O(1) de espacio adicional?

Sí, si puedes cambiar la entrada. La pila nunca contiene más dígitos de los que has leído, así que puede estar al principio del propio arreglo de dígitos, con un índice para su cima. Los lenguajes con cadenas inmutables siguen necesitando una copia de los dígitos, lo que es O(n).

def removeKdigits(num, k):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

num = "4325043"
k = 3

Salida Esperada

"2043"