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 une seule fois, et utilise un espace supplémentaire de O(1) : un compteur pour la séquence en cours et un pour la meilleure. Recommencer le comptage à chaque indice prend 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 à cet endroit est 0 , aucune séquence de 1 ne s’y termine, donc la longueur est 0 . Le 1 suivant la fait passer à 1 , la longueur de la nouvelle séquence.

Q: Le problème du nombre maximal de 1 consécutifs est-il un problème de fenêtre glissante ?

Tu peux le voir comme une fenêtre : elle contient la séquence actuelle, son bord droit avance à chaque valeur, et un 0 déplace le bord gauche au-delà de celui-ci. La fenêtre ne rétrécit jamais pas à pas, donc un compteur remplace les deux bords.

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 consécutifs, sans aucun 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équence 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: Le 1 seul à l’index 1 perd face à la paire aux index 3 et 4, donc la réponse est 2.

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

Pour aller plus loin

Et si tu pouvais convertir jusqu’à k zéros en uns ? Quelle longueur la plus longue séquence peut-elle atteindre, 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 suite prend fin dès qu’un 0 apparaît, donc à chaque indice, tu n’as besoin que de la longueur de la suite qui se termine à cet endroit. Un compteur qui augmente sur un 1 et revient à zéro sur un 0 permet de trouver la suite la plus longue en un seul passage.

Compter à partir de chaque indice

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Essaie chaque indice comme point de départ et avance tant que tu vois des 1 ; le nombre d’étapes correspond à la longueur de la suite qui commence à cet indice. La plus longue suite commence à l’un de ces indices, donc le plus grand nombre obtenu est la réponse.

Les parcours se chevauchent. Sur un tableau de n uns, ils prennent environ n² / 2 étapes, soit 2 × 10^8 pour n = 2 × 10^4.

Algorithme

Définis best = 0.
Pour chaque index start, définis length = 0.
Tant que start + length se trouve dans le tableau et que nums[start + length] vaut 1, ajoute 1 à length.
Garde la plus grande valeur entre best et length.
Retourne 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 seul passage avec un compteur cumulatif

Intuition

Conservez current, la longueur de la série de 1 qui se termine à l’indice où vous vous trouvez. Un 1 prolonge cette série d’une unité ; un 0 y met fin, donc current passe à 0. Chaque série est mesurée à son dernier indice, où current est égal à sa longueur totale ; la plus grande valeur atteinte par current est donc la réponse.

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.

Algorithme

Définis best = 0 et current = 0.
Pour chaque valeur de nums : si elle vaut 1, ajoute 1 à current et conserve la plus grande valeur entre best et current.
Si elle vaut 0, définis current = 0.
Renvoie 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

Mettre à jour best uniquement lorsque tu rencontres un 0. Une séquence qui atteint la fin, comme dans [0, 1, 1], n'est jamais enregistrée. Mets à jour après chaque 1, ou effectue une comparaison supplémentaire après la boucle.
Ne pas réinitialiser current sur un 0. Les séquences distinctes s'additionnent, et [1, 1, 0, 1, 1] renvoie 4.
Initialiser best à 1 ou à nums[0]. [0, 0, 0] doit renvoyer 0.
En Lua et en R, où les tableaux commencent à 1, borner le parcours vers l'avant avec < n au lieu de ≤ n. La dernière valeur n'est jamais lue, donc [0, 1] renvoie 0.

Questions fréquentes3

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 une seule fois, et utilise un espace supplémentaire de O(1) : un compteur pour la séquence en cours et un pour la meilleure. Recommencer le comptage à chaque indice prend 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 à cet endroit est 0, aucune séquence de 1 ne s’y termine, donc la longueur est 0. Le 1 suivant la fait passer à 1, la longueur de la nouvelle séquence.

Le problème du nombre maximal de 1 consécutifs est-il un problème de fenêtre glissante ?

Tu peux le voir comme une fenêtre : elle contient la séquence actuelle, son bord droit avance à chaque valeur, et un 0 déplace le bord gauche au-delà de celui-ci. La fenêtre ne rétrécit jamais pas à pas, donc un compteur remplace les deux bords.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu