Max Consecutive Ones

Q: Qual é a complexidade de tempo de Máximos de Uns Consecutivos?

A solução de uma única passagem é executada em tempo O(n) , porque lê cada valor uma vez, e usa O(1) de espaço extra: um contador para a sequência atual e outro para a melhor. Reiniciar a contagem em cada índice leva 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 nesse ponto é 0 , nenhuma sequência de 1s termina ali, então o comprimento é 0 . O próximo 1 eleva o valor para 1 , o comprimento da nova sequência.

Q: Max Consecutive Ones é um problema de janela deslizante?

Você pode enxergá-la como uma só: a janela contém a execução atual, sua borda direita avança a cada valor, e um 0 move a borda esquerda para além dele. A janela nunca diminui passo a passo, então um contador substitui as duas bordas.

InicianteArrays e strings

+10

Você recebe um array nums no qual 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: dos índices 0 a 1 (comprimento 2), de 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: O 1 solitário no índice 1 perde para o par nos índices 3 e 4, então a resposta é 2.

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

Para ir além

E se você puder transformar até k zeros em uns? Qual pode ser o tamanho da sequência mais longa, e você ainda consegue 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, em cada índice, você só precisa do comprimento da sequência que termina ali. Um contador que aumenta quando encontra um 1 e é zerado quando encontra um 0 encontra a sequência mais longa em uma única passagem.

Conte em ordem crescente a partir de cada índice

Correta, mas não termina nos maiores testes

Intuição

Experimente cada índice como início e avance enquanto encontrar 1s; o número de passos é o comprimento da sequência que começa ali. A sequência mais longa começa em um desses índices, então a maior contagem é a resposta.

Os percursos se sobrepõem. Em um array de n uns, eles levam cerca de n² / 2 passos, 2 × 10^8 para n = 2 × 10^4.

Algoritmo

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

Mantenha current, o comprimento da sequência de 1s que termina no índice em que você está. Um 1 estende essa sequência em um; um 0 a encerra, então current cai para 0. Cada sequência é medida em seu último índice, onde current é igual ao seu comprimento total, então o maior valor que current alcança é a resposta.

Em [1, 1, 0, 1, 1, 1, 0, 1], current assume os valores 1, 2, 0, 1, 2, 3, 0, 1, e o maior é 3.

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

Atualizar best somente quando encontrar um 0. Uma sequência que chega ao fim, como em [0, 1, 1], nunca é registrada. Atualize após cada 1 ou faça mais uma comparação após o loop.
Não redefinir current ao encontrar um 0. Sequências separadas são somadas, e [1, 1, 0, 1, 1] retorna 4.
Inicializar best com 1 ou com nums[0]. [0, 0, 0] deve retornar 0.
Em Lua e R, nas quais os arrays começam em 1, limitar a varredura para frente com < n em vez de ≤ n. O último valor nunca é lido, então [0, 1] retorna 0.

Perguntas frequentes3

Qual é a complexidade de tempo de Máximos de Uns Consecutivos?

A solução de uma única passagem é executada em tempo O(n), porque lê cada valor uma vez, e usa O(1) de espaço extra: um contador para a sequência atual e outro para a melhor. Reiniciar a contagem em cada índice leva 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 nesse ponto é 0, nenhuma sequência de 1s termina ali, então o comprimento é 0. O próximo 1 eleva o valor para 1, o comprimento da nova sequência.

Max Consecutive Ones é um problema de janela deslizante?

Você pode enxergá-la como uma só: a janela contém a execução atual, sua borda direita avança a cada valor, e um 0 move a borda esquerda para além dele. A janela nunca diminui passo a passo, então um contador substitui as duas bordas.

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada