Leaders in an Array

+10

Você recebe um array de números inteiros nums. Um elemento é um líder quando é maior ou igual a todos os elementos à sua direita. O último elemento não tem nada à sua direita, então ele é sempre um líder. Retorne todos os líderes, na ordem em que aparecem em nums, da esquerda para a direita.

Função

leaders(nums: integer-array) → integer-array

numsinteger-array: o array de inteiros a ser pesquisado
Retornainteger-array: os líderes de nums, da esquerda para a direita

Restrições

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Exemplos

Entrada: nums = [12, 5, 9, 3, 6, 2]
Saída: [12, 9, 6, 2]
Explicação: 2 é o último, então ele lidera. 6 vence o 2 que vem depois dele, 9 vence 3, 6 e 2, e 12 vence todos. 5 perde para 9 e 3 perde para 6, então a resposta é [12, 9, 6, 2].

Para ir além

Se os valores chegam um de cada vez e, após cada um, você precisa informar os líderes até o momento, como atualizar a lista em tempo amortizado O(1) por valor?

Dicas

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

0 de 3 abertas

Solução

Lendo da esquerda para a direita, cada elemento exige uma nova verificação do seu sufixo. Percorra da direita para a esquerda: a única coisa que você precisa saber sobre o sufixo é seu maior valor, e uma variável o armazena. Isso transforma uma verificação O(n²) em uma única passagem.

Verifique tudo à direita

Correta, mas não termina nos maiores testes

Intuição

Aplique a definição: para cada índice i, percorra os elementos seguintes e pare no primeiro que seja estritamente maior que nums[i]. Se a varredura chegar ao fim, nums[i] é líder. Você testa os índices da esquerda para a direita, então os líderes aparecem em ordem. Em [12, 5, 9, 3, 6, 2], 5 para em 9 e 3 para em 6.

O custo está nas varreduras que chegam ao fim. Com 24.999 valores iguais seguidos por um valor maior, cada elemento percorre quase todo o array: cerca de 25.000 × 25.000 / 2, mais de 3 × 10^8 comparações.

Algoritmo

Crie uma lista de resultados vazia.
Para cada índice i, percorra j de i + 1 até o fim.
Se algum nums[j] for maior que nums[i], pare: nums[i] não é um líder.
Se não existir tal j, adicione nums[i] ao resultado.
Retorne o resultado.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Uma passagem da direita com um máximo acumulado

Intuição

Ser pelo menos tão grande quanto cada elemento à direita é o mesmo que ser pelo menos tão grande quanto o máximo deles. Percorrendo da direita para a esquerda, você pode manter esse máximo atualizado. O último elemento lidera e inicia o máximo. Cada elemento à sua esquerda lidera quando é pelo menos tão grande quanto o máximo e, então, torna-se o novo máximo; caso contrário, há um valor maior à sua direita.

Em [12, 5, 9, 3, 6, 2]: 2 lidera, depois 6, depois 9 e, por fim, 12, enquanto 3 e 5 ficam abaixo do máximo. Você encontrou [2, 6, 9, 12]; invertido, esse é o resultado.

Cada elemento é comparado uma vez: tempo O(n) e espaço extra O(1), além do resultado. A versão em R marca os líderes em um vetor logical(n), então seu espaço extra é O(n).

Algoritmo

Coloque o último elemento no resultado e defina best como ele.
Mova i do penúltimo índice até 0.
Se nums[i] ≥ best, adicione nums[i] ao resultado e defina best como ele.
Inverta o resultado para que os líderes sejam lidos da esquerda para a direita e retorne-o.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Armadilhas e casos extremos

Usar > em vez de ≥ em relação ao máximo atual. Em [4, 7, 7, 1, 7], todos os 7 são líderes, mas uma comparação estrita mantém apenas o último.
Começar o máximo em 0 em vez de no último elemento. [-1, -5] deve retornar ambos, mas um máximo de 0 os descarta.
Retornar os líderes na ordem em que foram encontrados, [2, 6, 9, 12] em vez de [12, 9, 6, 2].
Adicionar o último elemento duas vezes começando o loop no último índice depois de já tê-lo colocado no resultado.
Comparar cada elemento apenas com seu vizinho. Em [5, 3, 9], 5 supera o 3 ao lado dele, mas o 9 faz com que a resposta seja [9].

Perguntas frequentes3

Qual é a complexidade de tempo para encontrar líderes em um array?

O(n) com uma única passagem da direita para a esquerda, porque cada elemento é comparado uma vez com o máximo acumulado. Verificar cada elemento em relação a tudo o que está à sua direita custa O(n²) no pior caso, por exemplo, quando todos os valores são iguais.

O último elemento é sempre um líder?

Sim. Um líder deve ser pelo menos tão grande quanto cada elemento à sua direita, e o último elemento não tem nenhum, então a condição é satisfeita sem nada para verificar.

Valores iguais contam como líderes?

Aqui, sim: um líder deve ser maior ou igual a todos os elementos à sua direita, então, em [4, 7, 7, 1, 7], os três 7s são líderes. Algumas versões exigem que seja estritamente maior; nesse caso, compare com >, e apenas o último dos valores empatados é líder.

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

Teste #1

Teste #2

Teste #3

Argumento

nums = [12, 5, 9, 3, 6, 2]

Saída Esperada

[12, 9, 6, 2]