Remove K Digits

Q: Quelle est la complexité temporelle de Remove K Digits ?

Avec une pile monotone, l’algorithme s’exécute en O(n) pour n chiffres : chaque chiffre est empilé une fois, et chaque dépilement utilise l’une des k suppressions. La pile contient jusqu’à n chiffres, donc l’espace supplémentaire est de O(n) . Rebalayer depuis la gauche pour chaque suppression coûte O(n·k) .

MoyenPile monotone Glouton

+10

On vous donne un nombre non négatif écrit sous forme de chaîne de chiffres, num, et un entier k. Supprimez exactement k chiffres et conservez les autres dans leur ordre d’origine, de façon à obtenir le plus petit nombre possible.

Renvoyez-le sous forme de chaîne sans zéros en tête. S’il ne reste rien, ou qu’il ne reste que des zéros, renvoyez "0".

Fonction

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

numstring: le nombre, écrit sous forme de chaîne de chiffres
kinteger: combien de chiffres supprimer
Renvoiestring: le plus petit nombre que vous pouvez laisser, sous forme de chaîne sans zéros initiaux

Contraintes

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num ne contient que les chiffres 0 à 9.
num n'a pas de zéros initiaux, sauf lorsqu'il s'agit du nombre zéro lui-même, "0".

Exemples

Entrée: num = "4325043"k = 3
Sortie: "2043"
Explication: Supprimer le 4 et le premier 3 place le 2 devant. Le 0 ne peut pas être en tête : quatre chiffres le précèdent et tu as trois suppressions. La dernière suppression enlève le 5, qui se trouve avant un 0 plus petit.

Entrée: num = "30200"k = 1
Sortie: "200"
Explication: Supprimer le 3 laisse 0200, soit 200 sans son zéro initial. Toute autre suppression garde le 3 devant et laisse un nombre à quatre chiffres, comme 3000.

Entrée: num = "52"k = 2
Sortie: "0"
Explication: Les deux chiffres sont supprimés, il ne reste donc rien et la réponse est "0".

Pour aller plus loin

Comment modifierais-tu la solution pour supprimer k chiffres et laisser le plus grand nombre à la place ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Les chiffres les plus à gauche ont le plus de poids, donc le premier chiffre plus grand que son voisin de droite doit être supprimé. Une pile des chiffres que tu conserves applique cette règle à toute la chaîne en un seul passage. Les suppressions restantes à la fin se font par l’arrière, puis les zéros en tête sont supprimés en dernier.

Supprimer un chiffre à la fois

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Supprimez un chiffre à la fois : trouvez la première position i où num[i] > num[i+1] et supprimez num[i], ou supprimez le dernier chiffre si les chiffres ne diminuent jamais. Répétez k fois.

Chaque réponse conserve n-k chiffres, donc la première position où deux réponses diffèrent détermine laquelle est la plus petite. Jusqu’à i, les chiffres ne diminuent jamais, donc supprimer un chiffre plus tôt fait glisser à sa place un chiffre au moins aussi grand ; supprimer un chiffre plus tard laisse le grand num[i] en place. Supprimer num[i] réduit la première position qui peut l’être.

Chaque suppression relance le parcours depuis la gauche et décale les chiffres qui suivent ; le travail est donc de O(n·k). Avec 40 000 chiffres 1 et k = 25,000, les parcours lisent environ 6.9 × 10^8 chiffres.

Algorithme

Copie les chiffres dans une liste à partir de laquelle tu peux supprimer des éléments.
Répète k fois : parcours la liste depuis la gauche jusqu'au premier chiffre supérieur au suivant, ou jusqu'au dernier chiffre, puis supprime-le.
Supprime les zéros initiaux et renvoie "0" s'il ne reste rien.

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"

Pile monotone de chiffres conservés

Intuition

Après que la version lente a supprimé num[i], les chiffres avant i ne diminuent toujours jamais ; la prochaine baisse ne peut donc commencer qu’au chiffre précédant le trou. Une pile contient ce préfixe : les chiffres conservés, qui ne diminuent jamais du bas vers le haut. Lorsqu’un nouveau chiffre est plus petit que le sommet, celui-ci est plus grand que son voisin de droite, le chiffre que la version lente supprimerait. Dépile-le, consomme une suppression, et continue à dépiler tant que le nouveau sommet est encore plus grand.

Pour 4325043 avec k = 3, le 3 dépile le 4, le 2 dépile le 3 et le 0 dépile le 5. Le 4 et le 3 sont empilés au fur et à mesure, ce qui donne 2043.

Chaque chiffre est empilé une fois et chaque dépilement consomme l’une des k suppressions ; le parcours est donc en O(n).

Algorithme

Crée une pile vide de chiffres.
Pour chaque chiffre de num : tant qu’il reste des suppressions et que le sommet de la pile est supérieur au chiffre, dépile le sommet et utilise une suppression. Empile ensuite le chiffre.
S’il reste des suppressions après la boucle, supprime autant de chiffres au sommet de la pile.
Lis la pile du bas vers le haut, ignore les zéros initiaux et renvoie le reste, ou "0" s’il ne reste rien.

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"

Pièges et cas limites

Dépiler lorsque le sommet est égal au nouveau chiffre. Avec 112 et k = 1, il reste 12 ; la bonne réponse est 11.
Oublier les suppressions restantes après la boucle, ou les effectuer depuis le début. La pile ne diminue jamais, donc ses derniers chiffres sont conservés : avec 123456789 et k = 3, on obtient 123456.
Compter les zéros supprimés comme des suppressions. Avec 100200 et k = 1, le 1 est la seule suppression ; les zéros au début sont supprimés gratuitement, et la réponse est 200.
Renvoyer une chaîne vide. Avec 10 et k = 1, il ne reste qu’un zéro, donc la réponse est "0".
Convertir num en entier. Il peut comporter 4 × 10^4 chiffres, bien au-delà de la capacité de tout type entier ; comparez donc les chiffres en tant que caractères.

Questions fréquentes3

Quelle est la complexité temporelle de Remove K Digits ?

Avec une pile monotone, l’algorithme s’exécute en O(n) pour n chiffres : chaque chiffre est empilé une fois, et chaque dépilement utilise l’une des k suppressions. La pile contient jusqu’à n chiffres, donc l’espace supplémentaire est de O(n). Rebalayer depuis la gauche pour chaque suppression coûte O(n·k).

Comment gérer les zéros en tête dans Remove K Digits ?

Supprimez d’abord les chiffres, puis retirez les zéros uniquement à la fin. Un zéro au début ne change pas la valeur, donc il ne coûte aucune suppression : 10200 avec k = 1 devient 0200, puis 200. Si la suppression ne laisse rien, renvoyez "0".

Peut-on résoudre « Supprimer K chiffres » avec un espace supplémentaire en O(1) ?

Oui, si tu peux modifier l’entrée. La pile ne contient jamais plus de chiffres que tu n’en as lus, donc elle peut occuper le début du tableau de chiffres lui-même, avec un index pour son sommet. Les langages où les chaînes sont immuables nécessitent tout de même une copie des chiffres, ce qui représente O(n).

def removeKdigits(num, k):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

num = "4325043"
k = 3

Résultat attendu

"2043"