Max Consecutive Ones

Q: ¿Cuál es la complejidad temporal de Max Consecutive Ones?

La solución de una pasada se ejecuta en tiempo O(n) , porque lee cada valor una vez, y usa O(1) de espacio adicional: un contador para la secuencia actual y otro para la mejor. Reiniciar el conteo en cada índice toma O(n²) en un arreglo compuesto solo por 1s.

Q: ¿Por qué el contador se restablece a 0 en lugar de a 1?

El contador almacena la longitud de la secuencia que termina en el índice actual. Cuando el valor allí es 0 , ninguna secuencia de unos termina allí, así que la longitud es 0 . El siguiente 1 lo aumenta a 1 , la longitud de la nueva secuencia.

Q: ¿Es «Max Consecutive Ones» un problema de ventana deslizante?

Puedes verlo como una ventana: contiene la racha actual, su borde derecho avanza con cada valor y un 0 mueve el borde izquierdo más allá de él. La ventana nunca se encoge paso a paso, así que un contador reemplaza los dos bordes.

PrincipianteArrays y cadenas

+10

Recibes un array nums en el que cada valor es 0 o 1. Una racha es una secuencia de unos que están uno al lado del otro, sin ningún 0 entre ellos. Devuelve la longitud de la racha más larga, o 0 si el array no contiene ningún 1.

Función

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: un arreglo de 0 y 1
Devuelveinteger: la longitud de la secuencia más larga de 1 consecutivos

Restricciones

1 ≤ nums.length ≤ 2 × 10⁴
Cada nums[i] es 0 o 1.

Ejemplos

Entrada: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Salida: 3
Explicación: Los 1 forman tres secuencias: los índices 0 a 1 (longitud 2), de 3 a 5 (longitud 3) y el índice 7 solo (longitud 1). La más larga tiene longitud 3.

Entrada: nums = [0, 1, 0, 1, 1]
Salida: 2
Explicación: El único 1 en el índice 1 pierde frente al par en los índices 3 y 4, así que la respuesta es 2.

Entrada: nums = [0, 0, 0]
Salida: 0
Explicación: No hay ningún 1 en ninguna parte, así que no hay ninguna secuencia y la respuesta es 0.

Para ir más allá

¿Qué pasa si puedes cambiar hasta k ceros por unos? ¿Cuánto puede llegar a medir la secuencia más larga y puedes encontrarla en una sola pasada?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una racha termina en el momento en que aparece un 0, así que en cada índice solo necesitas la longitud de la racha que termina ahí. Un contador que aumenta con un 1 y se reinicia con un 0 encuentra la racha más larga en una sola pasada.

Cuenta hacia adelante desde cada índice

Correcto, pero no termina con las pruebas más grandes

Intuición

Prueba cada índice como punto de partida y avanza mientras veas unos; el número de pasos es la longitud de la secuencia que comienza allí. La secuencia más larga comienza en uno de estos índices, así que el recuento más alto es la respuesta.

Los recorridos se superponen. En un arreglo de n unos, dan aproximadamente n² / 2 pasos, 2 × 10^8 para n = 2 × 10^4.

Algoritmo

Establece best = 0.
Para cada índice start, establece length = 0.
Mientras start + length esté dentro del array y nums[start + length] sea 1, suma 1 a length.
Conserva el mayor valor entre best y length.
Devuelve 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

Una pasada con un contador acumulado

Intuición

Mantén current, la longitud de la secuencia de 1 que termina en el índice en el que estás. Un 1 amplía esa secuencia en uno; un 0 la termina, así que current pasa a ser 0. Cada secuencia se mide en su último índice, donde current es igual a su longitud completa, así que el mayor valor que alcanza current es la respuesta.

En [1, 1, 0, 1, 1, 1, 0, 1], current toma los valores 1, 2, 0, 1, 2, 3, 0, 1, y el mayor es 3.

Algoritmo

Establece best = 0 y current = 0.
Para cada valor de nums: si es 1, suma 1 a current y conserva el mayor entre best y current.
Si es 0, establece current = 0.
Devuelve 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

Errores comunes y casos límite

Actualizar best solo cuando encuentres un 0. Nunca se registra una secuencia que llega hasta el final, como en [0, 1, 1]. Actualiza después de cada 1 o vuelve a comparar una vez más después del bucle.
No restablecer current al encontrar un 0. Las secuencias separadas se suman, y [1, 1, 0, 1, 1] devuelve 4.
Iniciar best en 1 o en nums[0]. [0, 0, 0] debe devolver 0.
En Lua y R, donde los arreglos comienzan en 1, limitar el recorrido hacia adelante con < n en lugar de ≤ n. Nunca se lee el último valor, por lo que [0, 1] devuelve 0.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Max Consecutive Ones?

La solución de una pasada se ejecuta en tiempo O(n), porque lee cada valor una vez, y usa O(1) de espacio adicional: un contador para la secuencia actual y otro para la mejor. Reiniciar el conteo en cada índice toma O(n²) en un arreglo compuesto solo por 1s.

¿Por qué el contador se restablece a 0 en lugar de a 1?

El contador almacena la longitud de la secuencia que termina en el índice actual. Cuando el valor allí es 0, ninguna secuencia de unos termina allí, así que la longitud es 0. El siguiente 1 lo aumenta a 1, la longitud de la nueva secuencia.

¿Es «Max Consecutive Ones» un problema de ventana deslizante?

Puedes verlo como una ventana: contiene la racha actual, su borde derecho avanza con cada valor y un 0 mueve el borde izquierdo más allá de él. La ventana nunca se encoge paso a paso, así que un contador reemplaza los dos bordes.

def findMaxConsecutiveOnes(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada