Max Consecutive Ones

Q: Quelle est la complexité temporelle de Max Consecutive Ones ?

La solution en un seul passage s’exécute en temps O(n) , car elle lit chaque valeur exactement une fois. Elle utilise un espace supplémentaire de O(1) : un compteur pour la série en cours et un pour la meilleure série. Recommencer le comptage à chaque indice prend un temps de O(n²) sur un tableau composé uniquement de 1.

Q: Pourquoi le compteur se réinitialise-t-il à 0 au lieu de 1 ?

Le compteur contient la longueur de la séquence qui se termine à l’index actuel. Lorsque la valeur actuelle est 0 , aucune séquence de 1 ne s’y termine, donc sa longueur est 0 . Le 1 suivant le fait alors passer à 1 , ce qui correspond à la longueur correcte d’une nouvelle séquence.

Q: Est-ce un problème de fenêtre glissante ?

Tu peux le voir comme une fenêtre : elle contient la séquence actuelle, le bord droit avance à chaque valeur, et un 0 fait passer le bord gauche au-delà. Ici, la fenêtre n’a jamais besoin de rétrécir pas à pas, donc un simple compteur remplace les deux bords. La représentation par fenêtre est utile dans la version plus difficile, où tu peux convertir jusqu’à k zéros en uns.

Q: Comment compter les 1 consécutifs si tu peux retourner un 0 ?

Gardez deux compteurs : la longueur de la séquence qui se termine ici sans inversion, et celle avec une inversion déjà utilisée. Sur un 1, les deux augmentent de un. Sur un 0, le compteur avec inversion devient le compteur sans inversion plus un, et le compteur sans inversion est réinitialisé à 0. La réponse est le plus grand compteur avec inversion que vous observez, toujours en un seul passage.

DébutantTableaux et chaînes

+10

Vous obtenez un tableau nums dans lequel chaque valeur est 0 ou 1. Une séquence est une suite de 1 côte à côte, sans 0 entre eux. Renvoyez la longueur de la plus longue séquence, ou 0 si le tableau ne contient aucun 1.

Fonction

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: un tableau de 0 et de 1
Renvoieinteger: la longueur de la plus longue série de 1 consécutifs

Contraintes

1 ≤ nums.length ≤ 2 × 10⁴
Chaque nums[i] vaut 0 ou 1.

Exemples

Entrée: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Sortie: 3
Explication: Les 1 forment trois séquences : des index 0 à 1 (longueur 2), de 3 à 5 (longueur 3) et l’index 7 seul (longueur 1). La plus longue a une longueur de 3.

Entrée: nums = [0, 1, 0, 1, 1]
Sortie: 2
Explication: Les séquences sont le 1 isolé à l’index 1 et la paire aux index 3 et 4. La paire l’emporte avec une longueur de 2.

Entrée: nums = [0, 0, 0]
Sortie: 0
Explication: Il n’y a aucun 1, donc il n’y a pas de séquence et la réponse est 0.

+14 tests cachés à la soumission

Pour aller plus loin

Et si tu pouvais transformer jusqu’à k zéros en uns ? Quelle longueur peut atteindre la plus longue série de 1, et peux-tu toujours la trouver en un seul passage ?

Indices

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

0 sur 3 ouverts

Solution

Une séquence se termine dès qu’un 0 apparaît, donc la seule chose que tu dois connaître à chaque indice est la longueur de la séquence qui s’y termine. Recompter depuis le début à chaque indice répète sans cesse le même travail. Un compteur qui augmente lorsqu’un 1 apparaît et revient à zéro lorsqu’un 0 apparaît répond à la question en un seul passage.

Comptez vers l’avant à partir de chaque indice

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Chaque séquence commence quelque part. Essaie donc chaque index comme point de départ et avance tant que tu rencontres des 1 ; le nombre d’étapes correspond à la longueur de la séquence qui commence à cet endroit. Le plus grand compte parmi tous les points de départ est la réponse. Pour [1, 1, 0, 1, 1, 1, 0, 1], le départ à l’index 3 parcourt trois 1 avant de rencontrer le 0 à l’index 6, ce qui donne 3.

La réponse est correcte, car la plus longue séquence commence à l’un des index que tu essaies, et le parcours depuis son premier index en mesure exactement la longueur.

Le coût se cache dans les chevauchements. Dans un tableau de n 1, le départ à l’index 0 parcourt n étapes, le suivant n-1, et ainsi de suite, soit environ n² / 2 étapes au total. Pour n = 2 × 10^4, cela représente 2 × 10^8 étapes, trop pour la limite de temps dans les langages plus lents.

Algorithme

Définissez best = 0.
Pour chaque indice start, définissez length = 0.
Tant que start + length se trouve dans le tableau et que nums[start + length] vaut 1, ajoutez 1 à length.
Conservez la plus grande valeur entre best et length.
Retournez best.

def findMaxConsecutiveOnes(nums):
    n = len(nums)
    best = 0
    for start in range(n):
        length = 0
        while start + length < n and nums[start + length] == 1:
            length += 1
        best = max(best, length)
    return best

Un passage avec un décompte cumulatif

Intuition

Parcourez le tableau une seule fois et conservez current, la longueur de la séquence de 1 qui se termine à l’indice où vous vous trouvez. Un 1 prolonge cette séquence, donc current augmente de un. Un 0 y met fin, donc current revient à 0. Après chaque 1, comparez current à best.

Pour [1, 1, 0, 1, 1, 1, 0, 1], current prend les valeurs 1, 2, 0, 1, 2, 3, 0, 1, et la plus grande est 3. Chaque séquence est mesurée à son dernier indice, où current est égal à sa longueur totale : la meilleure valeur obtenue est donc celle de la plus longue séquence.

Chaque valeur est lue une seule fois, ce qui correspond à un temps en O(n), et deux entiers représentent toute la mémoire dont vous avez besoin.

Algorithme

Définissez best = 0 et current = 0.
Pour chaque valeur de nums : si elle vaut 1, ajoutez 1 à current et conservez la plus grande valeur entre best et current.
Si elle vaut 0, définissez current = 0.
Renvoyez best.

def findMaxConsecutiveOnes(nums):
    best = 0
    current = 0
    for x in nums:
        if x == 1:
            current += 1
            best = max(best, current)
        else:
            # A 0 breaks the run.
            current = 0
    return best

Pièges et cas limites

La version en un seul passage est courte ; les bugs viennent donc de l’endroit où tu mets à jour la réponse.

Mettre à jour best uniquement lorsque tu rencontres un 0. Une séquence qui atteint la fin du tableau, comme dans [0, 1, 1], n’est jamais enregistrée. Mets à jour après chaque 1, ou fais une comparaison supplémentaire après la boucle.
Oublier de réinitialiser current à 0, ce qui additionne les 1 de séquences distinctes et renvoie 4 pour [1, 1, 0, 1, 1].
Initialiser best à 1 ou à nums[0]. Un tableau composé uniquement de 0 doit renvoyer 0.
En Lua et en R, le tableau commence à l’indice 1 ; le parcours vers l’avant vérifie donc start + length ≤ n plutôt que < n.

Questions fréquentes4

Quelle est la complexité temporelle de Max Consecutive Ones ?

La solution en un seul passage s’exécute en temps O(n), car elle lit chaque valeur exactement une fois. Elle utilise un espace supplémentaire de O(1) : un compteur pour la série en cours et un pour la meilleure série. Recommencer le comptage à chaque indice prend un temps de O(n²) sur un tableau composé uniquement de 1.

Pourquoi le compteur se réinitialise-t-il à 0 au lieu de 1 ?

Le compteur contient la longueur de la séquence qui se termine à l’index actuel. Lorsque la valeur actuelle est 0, aucune séquence de 1 ne s’y termine, donc sa longueur est 0. Le 1 suivant le fait alors passer à 1, ce qui correspond à la longueur correcte d’une nouvelle séquence.

Est-ce un problème de fenêtre glissante ?

Tu peux le voir comme une fenêtre : elle contient la séquence actuelle, le bord droit avance à chaque valeur, et un 0 fait passer le bord gauche au-delà. Ici, la fenêtre n’a jamais besoin de rétrécir pas à pas, donc un simple compteur remplace les deux bords. La représentation par fenêtre est utile dans la version plus difficile, où tu peux convertir jusqu’à k zéros en uns.

Comment compter les 1 consécutifs si tu peux retourner un 0 ?

Gardez deux compteurs : la longueur de la séquence qui se termine ici sans inversion, et celle avec une inversion déjà utilisée. Sur un 1, les deux augmentent de un. Sur un 0, le compteur avec inversion devient le compteur sans inversion plus un, et le compteur sans inversion est réinitialisé à 0. La réponse est le plus grand compteur avec inversion que vous observez, toujours en un seul passage.

Python

def findMaxConsecutiveOnes(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [1, 1, 0, 1, 1, 1, 0, 1]

Attendu