Max Consecutive Ones

Q: Qual é a complexidade de tempo de Max Consecutive Ones?

A solução de passagem única é executada em tempo O(n) , pois lê cada valor exatamente uma vez. Ela usa espaço extra O(1) : um contador para a sequência atual e outro para a melhor. Reiniciar a contagem em cada índice leva tempo O(n²) em um array composto apenas por 1s.

Q: Por que o contador é redefinido para 0 em vez de 1?

O contador armazena o comprimento da sequência que termina no índice atual. Quando o valor atual é 0 , nenhuma sequência de 1s termina ali, então seu comprimento é 0 . O próximo 1 então aumenta o contador para 1 , que é o comprimento correto de uma nova sequência.

Q: Este é um problema de janela deslizante?

Você pode enxergá-la como uma janela: ela contém a sequência atual, a borda direita avança a cada valor, e um 0 faz a borda esquerda passar por ele. Aqui, a janela nunca precisa encolher passo a passo, então um único contador substitui as duas bordas. A abordagem da janela é útil na versão mais difícil, em que você pode transformar até k zeros em uns.

Q: Como contar 1s consecutivos se você pode inverter um 0?

Mantenha dois contadores: o comprimento da sequência que termina aqui sem inversão e com uma inversão já usada. Ao encontrar um 1, ambos aumentam em um. Ao encontrar um 0, o contador com inversão passa a ser o contador sem inversão mais um, e o contador sem inversão é zerado. A resposta é o maior contador com inversão que você encontrar, ainda em uma única passagem.

InicianteArrays e strings

+10

Você recebe um array nums em que cada valor é 0 ou 1. Uma sequência é um trecho de 1s consecutivos, sem nenhum 0 entre eles. Retorne o comprimento da sequência mais longa ou 0 se o array não contiver nenhum 1.

Função

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: um array de 0s e 1s
Retornainteger: o comprimento da maior sequência de 1s consecutivos

Restrições

1 ≤ nums.length ≤ 2 × 10⁴
Cada nums[i] é 0 ou 1.

Exemplos

Entrada: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Saída: 3
Explicação: Os 1s form três sequências: índices 0 a 1 (comprimento 2), 3 a 5 (comprimento 3) e o índice 7 sozinho (comprimento 1). A mais longa tem comprimento 3.

Entrada: nums = [0, 1, 0, 1, 1]
Saída: 2
Explicação: As sequências são o único 1 no índice 1 e o par nos índices 3 e 4. O par vence, com comprimento 2.

Entrada: nums = [0, 0, 0]
Saída: 0
Explicação: Não há nenhum 1, então não há nenhuma sequência, e a resposta é 0.

+14 testes ocultos ao enviar

Para ir além

E se você puder transformar até k zeros em uns? Qual pode ser o comprimento da maior sequência de 1s e ainda é possível encontrá-la em uma única passagem?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma sequência termina no momento em que aparece um 0, então a única coisa que você precisa saber em cada índice é qual é o comprimento da sequência que termina ali. Contar do zero em cada índice repete o mesmo trabalho várias vezes. Um contador que aumenta com um 1 e é zerado com um 0 responde à pergunta em uma única passagem.

Conte para frente a partir de cada índice

Correta, mas não termina nos maiores testes

Intuição

Toda sequência começa em algum lugar. Então, tente cada índice como início e avance enquanto continuar encontrando 1s; o número de passos é o comprimento da sequência que começa ali. A maior contagem entre todos os inícios é a resposta. Para [1, 1, 0, 1, 1, 1, 0, 1], o início no índice 3 percorre três 1s antes de encontrar o 0 no índice 6, o que resulta em 3.

A resposta está correta porque a sequência mais longa começa em um dos índices testados e, a partir do seu primeiro índice, o percurso mede seu comprimento exatamente.

O custo está na sobreposição. Em um array com n uns, o início no índice 0 percorre n passos, o seguinte percorre n-1 e assim por diante, totalizando cerca de n² / 2 passos. Para n = 2 × 10^4, isso representa 2 × 10^8 passos, demais para o limite de tempo em linguagens mais lentas.

Algoritmo

Defina best = 0.
Para cada índice start, defina length = 0.
Enquanto start + length estiver dentro do array e nums[start + length] for 1, adicione 1 a length.
Mantenha o maior entre best e length.
Retorne 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

Uma passagem com uma contagem contínua

Intuição

Percorra o array uma vez e mantenha current, o comprimento da sequência de 1s que termina no índice em que você está. Um 1 estende essa sequência, então current aumenta em um. Um 0 a encerra, então current volta a 0. Depois de cada 1, compare current com best.

Em [1, 1, 0, 1, 1, 1, 0, 1], current assume os valores 1, 2, 0, 1, 2, 3, 0, 1, e o maior deles é 3. Cada sequência é medida em seu último índice, onde current equivale ao seu comprimento total, então o melhor valor encontrado é o da sequência mais longa.

Cada valor é lido uma vez, o que corresponde a um tempo O(n), e dois inteiros são tudo de que você precisa de memória.

Algoritmo

Defina best = 0 e current = 0.
Para cada valor em nums: se for 1, some 1 a current e mantenha o maior valor entre best e current.
Se for 0, defina current = 0.
Retorne 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

Armadilhas e casos extremos

A versão de uma passagem é curta, então os bugs vêm de onde você atualiza a resposta.

Atualizar best somente quando você encontra um 0. Uma sequência que chega ao final do array, como em [0, 1, 1], nunca é registrada. Atualize após cada 1 ou compare mais uma vez depois do loop.
Esquecer de redefinir current ao encontrar um 0, o que soma os 1s de sequências separadas e retorna 4 para [1, 1, 0, 1, 1].
Começar best com 1 ou com nums[0]. Um array contendo apenas 0s deve retornar 0.
Em Lua e R, o array começa no índice 1, então a varredura para a frente verifica start + length ≤ n em vez de < n.

Perguntas frequentes4

Qual é a complexidade de tempo de Max Consecutive Ones?

A solução de passagem única é executada em tempo O(n), pois lê cada valor exatamente uma vez. Ela usa espaço extra O(1): um contador para a sequência atual e outro para a melhor. Reiniciar a contagem em cada índice leva tempo O(n²) em um array composto apenas por 1s.

Por que o contador é redefinido para 0 em vez de 1?

O contador armazena o comprimento da sequência que termina no índice atual. Quando o valor atual é 0, nenhuma sequência de 1s termina ali, então seu comprimento é 0. O próximo 1 então aumenta o contador para 1, que é o comprimento correto de uma nova sequência.

Este é um problema de janela deslizante?

Você pode enxergá-la como uma janela: ela contém a sequência atual, a borda direita avança a cada valor, e um 0 faz a borda esquerda passar por ele. Aqui, a janela nunca precisa encolher passo a passo, então um único contador substitui as duas bordas. A abordagem da janela é útil na versão mais difícil, em que você pode transformar até k zeros em uns.

Como contar 1s consecutivos se você pode inverter um 0?

Mantenha dois contadores: o comprimento da sequência que termina aqui sem inversão e com uma inversão já usada. Ao encontrar um 1, ambos aumentam em um. Ao encontrar um 0, o contador com inversão passa a ser o contador sem inversão mais um, e o contador sem inversão é zerado. A resposta é o maior contador com inversão que você encontrar, ainda em uma única passagem.

Python

def findMaxConsecutiveOnes(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado