Remove K Digits

Q: Wie hoch ist die Zeitkomplexität von Remove K Digits?

Mit einem monotonen Stack läuft es in O(n) Zeit für n Ziffern: Jede Ziffer wird einmal hinzugefügt, und jedes Entfernen verbraucht eine der k Entfernungen. Der Stack enthält bis zu n Ziffern, daher beträgt der zusätzliche Speicherplatz O(n) . Das erneute Durchlaufen von links für jede Entfernung kostet O(n·k) .

MittelMonotoner Stack Greedy

+10

Du erhältst eine nichtnegative Zahl, die als Zeichenfolge aus Ziffern geschrieben ist, num, und eine ganze Zahl k. Entferne genau k Ziffern und behalte die übrigen in ihrer ursprünglichen Reihenfolge bei, sodass die verbleibende Zahl so klein wie möglich ist.

Gib sie als Zeichenfolge ohne führende Nullen zurück. Wenn nichts übrig bleibt oder nur Nullen übrig bleiben, gib "0" zurück.

Funktion

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

numstring: die Zahl, als Ziffernfolge geschrieben
kinteger: wie viele Ziffern entfernt werden sollen
Gibt zurückstring: die kleinste Zahl, die du stehen lassen kannst, als Zeichenfolge ohne führende Nullen

Einschränkungen

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num enthält nur die Ziffern 0 bis 9.
num hat keine führenden Nullen, außer wenn es selbst die Zahl Null ist, "0".

Beispiele

Eingabe: num = "4325043"k = 3
Ausgabe: "2043"
Erklärung: Wenn du die 4 und die erste 3 entfernst, steht die 2 vorne. Die 0 kann nicht an erster Stelle stehen: Vier Ziffern stehen vor ihr, und du hast drei Entfernungen. Bei der letzten Entfernung nimmst du die 5, die vor einer kleineren 0 steht.

Eingabe: num = "30200"k = 1
Ausgabe: "200"
Erklärung: Wenn man die 3 entfernt, bleibt 0200 übrig, und ohne die führende Null ist das 200. Bei jeder anderen Entfernung bleibt die 3 vorne und es bleibt eine vierstellige Zahl wie 3000.

Eingabe: num = "52"k = 2
Ausgabe: "0"
Erklärung: Beide Ziffern werden entfernt, sodass nichts übrig bleibt und die Antwort "0" lautet.

Weiterführende Frage

Wie würdest du die Lösung ändern, um k Ziffern zu entfernen und stattdessen die größtmögliche Zahl zu erhalten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Ziffern ganz links haben das größte Gewicht, also sollte die erste Ziffer, die größer ist als ihr rechter Nachbar, entfernt werden. Ein Stapel der Ziffern, die du behältst, wendet diese Regel in einem Durchlauf auf die gesamte Zeichenfolge an. Am Ende noch ausstehende Entfernungen erfolgen von hinten, und führende Nullen werden zuletzt entfernt.

Entferne jeweils eine Ziffer

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Entferne jeweils eine Ziffer: Finde die erste Position i, an der num[i] > num[i+1] gilt, und lösche num[i]. Falls die Ziffern nie abnehmen, lösche die letzte Ziffer. Wiederhole dies k Mal.

Jede Antwort enthält n-k Ziffern, daher entscheidet die erste Position, an der sich zwei Antworten unterscheiden, welche kleiner ist. Bis i nehmen die Ziffern nie ab, daher rückt beim Löschen einer früheren Ziffer eine mindestens ebenso große Ziffer nach; beim Löschen einer späteren Ziffer bleibt die große Ziffer num[i] an Ort und Stelle. Das Löschen von num[i] verringert die frühestmögliche Position.

Bei jeder Entfernung wird von links an erneut gesucht und die Ziffern dahinter werden verschoben, daher beträgt der Aufwand O(n·k). Bei 40.000 Einsen und k = 25,000 lesen die Durchläufe etwa 6.9 × 10^8 Ziffern.

Algorithmus

Kopiere die Ziffern in eine Liste, aus der du löschen kannst.
Wiederhole k Mal: Gehe von links bis zur ersten Ziffer, die größer als die nächste ist, oder bis zur letzten Ziffer, und lösche sie.
Entferne die führenden Nullen und gib "0" zurück, wenn nichts übrig bleibt.

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"

Monotoner Stapel der beibehaltenen Ziffern

Idee

Nachdem die langsame Version num[i] löscht, werden die Ziffern vor i immer noch nie kleiner, daher kann der nächste Abstieg nur bei der Ziffer vor der Lücke beginnen. Ein Stapel speichert diesen Präfix: die beibehaltenen Ziffern, die von unten nach oben niemals kleiner werden. Wenn eine neue Ziffer kleiner als die oberste ist, ist die oberste größer als ihr rechter Nachbar, also der Ziffer, die die langsame Version löschen würde. Entferne sie vom Stapel, verbrauche eine Löschung und fahre mit dem Entfernen fort, solange die neue oberste Ziffer noch größer ist.

Bei 4325043 mit k = 3 entfernt die 3 die 4, die 2 entfernt die 3 und die 0 entfernt die 5. Die 4 und die 3 werden der Reihe nach auf den Stapel gelegt, sodass 2043 entsteht.

Jede Ziffer wird einmal auf den Stapel gelegt, und jedes Entfernen verbraucht eine der k Löschungen, daher ist der Durchlauf O(n).

Algorithmus

Erstelle einen leeren Ziffernstapel.
Für jede Ziffer von num: Solange noch Entfernungen übrig sind und die oberste Ziffer im Stapel größer als die Ziffer ist, entferne die oberste Ziffer und verbrauche eine Entfernung. Lege dann die Ziffer auf den Stapel.
Wenn nach der Schleife noch Entfernungen übrig sind, entferne entsprechend viele Ziffern von der Oberseite des Stapels.
Lies den Stapel von unten nach oben, überspringe die führenden Nullen und gib den Rest zurück, oder "0", falls nichts übrig ist.

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"

Stolperfallen und Grenzfälle

Entfernen, wenn die oberste Ziffer der neuen Ziffer entspricht. Bei 112 mit k = 1 bleibt dadurch 12 übrig; die richtige Antwort ist 11.
Die nach der Schleife verbleibenden Löschvorgänge vergessen oder sie am Anfang vornehmen. Der Stack wird nie kleiner, also lauten seine letzten Ziffern: 123456789 mit k = 3 ergibt 123456.
Entfernte Nullen als Löschvorgänge mitzählen. Bei 100200 mit k = 1 ist die 1 der einzige Löschvorgang; die Nullen vorne werden kostenlos entfernt, und die Antwort ist 200.
Einen leeren String zurückgeben. Bei 10 mit k = 1 bleibt nur eine Null übrig, also lautet die Antwort "0".
num in eine Ganzzahl umwandeln. Es kann 4 × 10^4 Ziffern haben, weit mehr, als ein Ganzzahltyp verarbeiten kann; vergleiche die Ziffern daher als Zeichen.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Remove K Digits?

Mit einem monotonen Stack läuft es in O(n) Zeit für n Ziffern: Jede Ziffer wird einmal hinzugefügt, und jedes Entfernen verbraucht eine der k Entfernungen. Der Stack enthält bis zu n Ziffern, daher beträgt der zusätzliche Speicherplatz O(n). Das erneute Durchlaufen von links für jede Entfernung kostet O(n·k).

Wie gehst du mit führenden Nullen bei „Remove K Digits“ um?

Entferne zuerst die Ziffern und streiche die Nullen erst am Ende. Eine Null am Anfang ändert den Wert nicht und kostet daher keine Entfernung: 10200 wird mit k = 1 zu 0200 und dann zu 200. Wenn nach dem Streichen nichts übrig bleibt, gib "0" zurück.

Kann man K Ziffern mit O(1) zusätzlichem Speicherplatz entfernen?

Ja, wenn du die Eingabe ändern darfst. Der Stack enthält nie mehr Ziffern, als du gelesen hast, daher kann er im vorderen Bereich des Ziffernarrays selbst liegen, mit einem Index für seine Spitze. Sprachen mit unveränderlichen Zeichenfolgen benötigen dennoch eine Kopie der Ziffern, was O(n) entspricht.

def removeKdigits(num, k):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

num = "4325043"
k = 3

Erwartete Ausgabe

"2043"