Remove K Digits

Q: Qual è la complessità temporale di Remove K Digits?

Con uno stack monotono, l’algoritmo richiede un tempo O(n) per n cifre: ogni cifra viene inserita una volta e ogni rimozione consuma una delle k rimozioni. Lo stack contiene fino a n cifre, quindi lo spazio aggiuntivo è O(n) . Riesaminare da sinistra a ogni rimozione richiede O(n·k) .

MedioStack monotono Greedy

+10

Ti viene dato un numero non negativo scritto come stringa di cifre, num, e un intero k. Rimuovi esattamente k cifre e mantieni le altre nel loro ordine originale, in modo che il numero rimanente sia il più piccolo possibile.

Restituiscilo come stringa senza zeri iniziali. Se non rimane nulla o rimangono solo zeri, restituisci "0".

Funzione

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

numstring: il numero, scritto come stringa di cifre
kinteger: quante cifre rimuovere
Restituiscestring: il numero più piccolo che puoi lasciare, come stringa senza zeri iniziali

Vincoli

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num contiene solo le cifre da 0 a 9.
num non ha zeri iniziali, tranne quando è il numero zero, "0".

Esempi

Input: num = "4325043"k = 3
Output: "2043"
Spiegazione: Eliminando il 4 e il primo 3, il 2 va davanti. Lo 0 non può essere in testa: davanti a lui ci sono quattro cifre e hai a disposizione tre rimozioni. L’ultima rimozione elimina il 5, che si trova prima di uno 0 più piccolo.

Input: num = "30200"k = 1
Output: "200"
Spiegazione: Rimuovendo il 3 si ottiene 0200 e, senza lo zero iniziale, 200. Qualsiasi altra rimozione mantiene il 3 davanti e lascia un numero di quattro cifre, come 3000.

Input: num = "52"k = 2
Output: "0"
Spiegazione: Entrambe le cifre vengono rimosse, quindi non rimane nulla e la risposta è "0".

Per approfondire

Come modificheresti la soluzione per rimuovere k cifre e lasciare il numero più grande?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Le cifre più a sinistra hanno il peso maggiore, quindi va rimossa la prima cifra più grande della sua vicina a destra. Una pila delle cifre che mantieni applica questa regola all’intera stringa in un solo passaggio. Le rimozioni rimanenti alla fine vengono effettuate dalla coda, e gli zeri iniziali vengono eliminati per ultimi.

Rimuovi una cifra alla volta

Corretto, ma non termina sui test più grandi

Intuizione

Rimuovi una cifra alla volta: trova la prima posizione i in cui num[i] > num[i+1] ed elimina num[i], oppure elimina l’ultima cifra se le cifre non diminuiscono mai. Ripeti k volte.

Ogni risposta mantiene n-k cifre, quindi la prima posizione in cui due risposte differiscono determina quale è più piccola. Fino a i le cifre non diminuiscono mai, quindi eliminare una cifra precedente fa subentrare una cifra almeno altrettanto grande; eliminare una cifra successiva lascia al suo posto la cifra grande num[i]. Eliminare num[i] abbassa la prima posizione che è possibile abbassare.

A ogni rimozione si esegue una nuova scansione da sinistra e si spostano le cifre successive, quindi il lavoro è O(n·k). Con 40,000 uno e k = 25,000, le scansioni leggono circa 6.9 × 10^8 cifre.

Algoritmo

Copia le cifre in una lista da cui puoi eliminare elementi.
Ripeti k volte: scorri da sinistra fino alla prima cifra più grande della successiva, oppure fino all’ultima cifra, ed eliminala.
Rimuovi gli zeri iniziali e restituisci "0" se non rimane nulla.

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"

Stack monotono delle cifre mantenute

Intuizione

Dopo che la versione lenta elimina num[i], le cifre prima di i continuano a non diminuire, quindi la successiva eliminazione può iniziare solo dalla cifra prima dello spazio vuoto. Una pila contiene quel prefisso: le cifre mantenute, in ordine non decrescente dal basso verso l’alto. Quando una nuova cifra è più piccola di quella in cima, la cifra in cima è maggiore della sua vicina a destra, cioè la cifra che la versione lenta eliminerebbe. Rimuovila, consuma una rimozione e continua a rimuovere finché la nuova cifra in cima è ancora maggiore.

Con 4325043 e k = 3, il 3 rimuove il 4, il 2 rimuove il 3 e lo 0 rimuove il 5. Il 4 e il 3 vengono inseriti man mano che arrivano, ottenendo 2043.

Ogni cifra viene inserita una volta e ogni rimozione consuma una delle k rimozioni, quindi il passaggio è O(n).

Algoritmo

Crea uno stack vuoto di cifre.
Per ogni cifra di num: mentre rimangono rimozioni e la cifra in cima allo stack è maggiore della cifra, rimuovi quella in cima e consuma una rimozione. Poi inserisci la cifra.
Se dopo il ciclo rimangono rimozioni, rimuovi quel numero di cifre dalla cima dello stack.
Leggi lo stack dal basso verso l'alto, salta gli zeri iniziali e restituisci il resto, oppure "0" se non rimane nulla.

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"

Trappole e casi limite

Rimuovere l'elemento in cima quando è uguale alla nuova cifra. Con 112 e k = 1, rimane 12; la risposta corretta è 11.
Dimenticare le rimozioni rimaste dopo il ciclo o rimuovere gli elementi dall'inizio. La pila non diminuisce mai, quindi le ultime cifre sono: con 123456789 e k = 3 si ottiene 123456.
Contare gli zeri iniziali rimossi come rimozioni. Con 100200 e k = 1, l'unica rimozione è l'1; gli zeri iniziali vengono eliminati senza costi e la risposta è 200.
Restituire una stringa vuota. Con 10 e k = 1 rimane solo uno zero, quindi la risposta è "0".
Convertire num in un intero. Può avere 4 × 10^4 cifre, ben oltre qualsiasi tipo intero, quindi confronta le cifre come caratteri.

Domande frequenti3

Qual è la complessità temporale di Remove K Digits?

Con uno stack monotono, l’algoritmo richiede un tempo O(n) per n cifre: ogni cifra viene inserita una volta e ogni rimozione consuma una delle k rimozioni. Lo stack contiene fino a n cifre, quindi lo spazio aggiuntivo è O(n). Riesaminare da sinistra a ogni rimozione richiede O(n·k).

Come gestisci gli zeri iniziali in Remove K Digits?

Rimuovi prima le cifre e togli gli zeri solo alla fine. Uno zero davanti non cambia il valore, quindi non costa alcuna rimozione: 10200 con k = 1 diventa 0200 e poi 200. Se dopo aver tolto gli zeri non rimane nulla, restituisci "0".

È possibile risolvere «Rimuovere K cifre» con O(1) di spazio aggiuntivo?

Sì, se puoi modificare l’input. Lo stack non contiene mai più cifre di quante ne hai lette, quindi può stare all’inizio dell’array di cifre stesso, con un indice per la sua cima. I linguaggi con stringhe immutabili hanno comunque bisogno di una copia delle cifre, che è O(n).

def removeKdigits(num, k):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

num = "4325043"
k = 3

Output atteso

"2043"