Max Consecutive Ones

Q: ¿Cuál es la complejidad temporal de Máximo de unos consecutivos?

La solución de una pasada se ejecuta en tiempo O(n) , porque lee cada valor exactamente una vez. Usa espacio extra O(1) : un contador para la secuencia actual y otro para la mejor. Reiniciar el contador en cada índice requiere tiempo O(n²) en un array compuesto solo por 1.

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

El contador contiene la longitud de la secuencia que termina en el índice actual. Cuando el valor actual es 0 , ninguna secuencia de 1 termina ahí, así que su longitud es 0 . El siguiente 1 después lo incrementa a 1 , que es la longitud correcta de una nueva secuencia.

Q: ¿Es este un problema de ventana deslizante?

Puedes verlo como uno solo: la ventana contiene la secuencia actual, el borde derecho avanza con cada valor y un 0 desplaza el borde izquierdo más allá de él. Aquí la ventana nunca necesita encogerse paso a paso, así que un solo contador reemplaza los dos bordes. La vista de ventana resulta útil en la versión más difícil, donde puedes cambiar hasta k ceros por unos.

Q: ¿Cómo cuentas los 1 consecutivos si puedes cambiar un 0?

Mantén dos contadores: la longitud de la secuencia que termina aquí sin invertir ningún valor y con una inversión ya utilizada. Con un 1, ambos aumentan en uno. Con un 0, el contador con inversión pasa a ser el contador normal más uno, y el contador normal se reinicia a 0. La respuesta es el mayor contador con inversión que encuentres, todo en una sola pasada.

PrincipianteArrays y cadenas

+10

Recibes un arreglo nums en el que cada valor es 0 o 1. Una secuencia es un tramo de unos que están juntos, sin ningún 0 entre ellos. Devuelve la longitud de la secuencia más larga, o 0 si el arreglo 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: índices 0 a 1 (longitud 2), 3 a 5 (longitud 3) e índice 7 solo (longitud 1). La más larga tiene una longitud de 3.

Entrada: nums = [0, 1, 0, 1, 1]
Salida: 2
Explicación: Las rachas son el único 1 en el índice 1 y la pareja en los índices 3 y 4. La pareja gana con una longitud de 2.

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

+14 pruebas ocultas al enviar

Para ir más allá

¿Qué pasa si puedes convertir hasta k ceros en unos? ¿Cuánto puede llegar a medir la secuencia más larga de unos 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 secuencia termina en el momento en que aparece un 0, así que lo único que necesitas saber en cada índice es cuánto mide la secuencia que termina ahí. Contar desde cero en cada índice repite el mismo trabajo una y otra vez. Un contador que aumenta cuando aparece un 1 y se reinicia cuando aparece un 0 responde a la pregunta en una sola pasada.

Cuenta hacia adelante desde cada índice

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

Intuición

Cada secuencia empieza en algún lugar. Así que prueba cada índice como punto de partida y avanza mientras sigas viendo unos; el número de pasos es la longitud de la secuencia que empieza allí. El mayor recuento de todos los puntos de partida es la respuesta. Para [1, 1, 0, 1, 1, 1, 0, 1], desde el índice 3 se avanza sobre tres unos antes de encontrar el 0 en el índice 6, lo que da 3.

La respuesta es correcta porque la secuencia más larga empieza en uno de los índices que pruebas y, desde su primer índice, el recorrido mide su longitud exacta.

El coste está en la superposición. En un array de n unos, desde el índice 0 se recorren n pasos, desde el siguiente n-1, y así sucesivamente: unos n² / 2 pasos en total. Para n = 2 × 10^4, eso son 2 × 10^8 pasos, demasiados para el límite de tiempo en lenguajes más lentos.

Algoritmo

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

Recorre el arreglo una vez y 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, así que current aumenta en uno. Un 0 la termina, así que current vuelve a 0. Después de cada 1, compara current con best.

En [1, 1, 0, 1, 1, 1, 0, 1], current toma los valores 1, 2, 0, 1, 2, 3, 0, 1, y el mayor de ellos es 3. Cada secuencia se mide en su último índice, donde current equivale a su longitud total, así que el mejor valor observado es la secuencia más larga.

Cada valor se lee una vez, lo que requiere un tiempo de O(n), y solo necesitas dos enteros de memoria.

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

La versión de una sola pasada es breve, así que los errores se deben a dónde actualizas la respuesta.

Actualizar best solo cuando encuentras un 0. Nunca se registra una secuencia que llega hasta el final del array, como [0, 1, 1]. Actualiza después de cada 1 o vuelve a comparar una vez más después del bucle.
Olvidar restablecer current al encontrar un 0, lo que suma los 1 de secuencias separadas y devuelve 4 para [1, 1, 0, 1, 1].
Inicializar best en 1 o en nums[0]. Un array compuesto solo por 0 debe devolver 0.
En Lua y R, el array empieza en el índice 1, así que el recorrido hacia delante comprueba start + length ≤ n en lugar de < n.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Máximo de unos consecutivos?

La solución de una pasada se ejecuta en tiempo O(n), porque lee cada valor exactamente una vez. Usa espacio extra O(1): un contador para la secuencia actual y otro para la mejor. Reiniciar el contador en cada índice requiere tiempo O(n²) en un array compuesto solo por 1.

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

El contador contiene la longitud de la secuencia que termina en el índice actual. Cuando el valor actual es 0, ninguna secuencia de 1 termina ahí, así que su longitud es 0. El siguiente 1 después lo incrementa a 1, que es la longitud correcta de una nueva secuencia.

¿Es este un problema de ventana deslizante?

Puedes verlo como uno solo: la ventana contiene la secuencia actual, el borde derecho avanza con cada valor y un 0 desplaza el borde izquierdo más allá de él. Aquí la ventana nunca necesita encogerse paso a paso, así que un solo contador reemplaza los dos bordes. La vista de ventana resulta útil en la versión más difícil, donde puedes cambiar hasta k ceros por unos.

¿Cómo cuentas los 1 consecutivos si puedes cambiar un 0?

Mantén dos contadores: la longitud de la secuencia que termina aquí sin invertir ningún valor y con una inversión ya utilizada. Con un 1, ambos aumentan en uno. Con un 0, el contador con inversión pasa a ser el contador normal más uno, y el contador normal se reinicia a 0. La respuesta es el mayor contador con inversión que encuentres, todo en una sola pasada.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado