Last Stone Weight

Q: Qual é a complexidade de tempo de Last Stone Weight?

Com um max-heap, construir o heap e jogar no máximo n-1 rodadas, com duas remoções e uma inserção cada, leva tempo O(n log n) e espaço O(n) . Ordenar a pilha inteira a cada rodada, em vez disso, leva O(n² log n) .

FácilHeap

+10

Você tem uma pilha de pedras, e stones[i] é o peso da pedra i. A cada rodada, pegue as duas pedras mais pesadas e esmague-as juntas. Se elas tiverem o mesmo peso, ambas são destruídas. Caso contrário, a pedra mais leve é destruída e a mais pesada fica com o peso correspondente à diferença entre os dois pesos.

Escreva uma função chamada lastStoneWeight que jogue rodadas até restar no máximo uma pedra e retorne o peso dessa pedra, ou 0 quando não restar nenhuma pedra.

Função

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: os pesos das pedras na pilha
Retornainteger: o peso da última pedra, ou 0 se não restar nenhuma

Restrições

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Exemplos

Entrada: stones = [3, 9, 4, 6, 2]
Saída: 0
Explicação: 9 e 6 deixam uma 3, depois 4 e 3 deixam uma 1, depois 3 e 2 deixam outra 1. As duas pedras de peso 1 se destroem mutuamente, então não sobra nada e a resposta é 0.

Entrada: stones = [10, 4, 1]
Saída: 5
Explicação: 10 e 4 deixam uma pedra de 6, e 6 e 1 deixam uma pedra de 5. Resta uma pedra, pesando 5.

Entrada: stones = [8]
Saída: 8
Explicação: Uma única pedra não tem nada contra o que ser esmagada, então seu peso 8 é a resposta.

+13 testes ocultos ao enviar

Para ir além

Os pesos são no máximo 1000. Você consegue usar esse limite para concluir em O(n + W) tempo, em que W é o maior peso, sem usar um heap?

Dicas

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

0 de 3 abertas

Solução

As regras são uma simulação: não há fórmula para avançar, então você joga todas as rodadas. Em cada rodada, são necessárias as duas pedras mais pesadas de um monte que está sempre mudando, porque uma pedra esmagada pode voltar mais leve. Ordenar novamente a cada rodada permite encontrá-las, mas custa O(n log n) por rodada. Um heap máximo fornece a pedra mais pesada e recebe outra em O(log n).

Organize a pilha a cada rodada

Correta, mas não termina nos maiores testes

Intuição

Siga as regras literalmente. Ordene a pilha para que as duas pedras mais pesadas fiquem no final, retire-as e, se os pesos forem diferentes, coloque a diferença de volta. Repita até que a pilha tenha uma ou nenhuma pedra.

A diferença pode ficar em qualquer posição na ordem. No primeiro exemplo, 9 e 6 deixam 3, que deve ficar abaixo de 4; portanto, você ordena novamente antes da próxima rodada para encontrar as duas pedras mais pesadas.

Cada rodada remove pelo menos uma pedra, então há até n-1 rodadas, cada uma com uma ordenação de até n pedras: O(n² log n). Com n = 10^4, isso representa cerca de 10^4 ordenações de até 10^4 números, pelo menos 5 × 10^7 etapas mesmo quando a ordenação percebe que a lista está quase ordenada, e várias vezes mais quando não percebe. Isso é lento demais para os maiores testes, enquanto a heap abaixo precisa de apenas algumas centenas de milhares de etapas.

Algoritmo

Copie as pedras para uma lista chamada pile.
Enquanto a pilha tiver mais de uma pedra, ordene-a em ordem crescente.
Retire as duas últimas pedras, heaviest e second.
Se forem diferentes, adicione heaviest - second de volta à pilha.
Retorne a pedra restante ou 0 quando a pilha estiver vazia.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Max-heap

Intuição

A cada rodada, você só precisa das pedras mais pesadas, nunca da ordem completa. Para isso, usa-se um heap máximo: ele mantém o maior valor no topo, e remover o topo ou adicionar um valor custa O(log n).

Coloque todas as pedras no heap. A cada rodada, remova duas para obter as duas mais pesadas. Se forem diferentes, insira a diferença de volta; o heap a move para a posição correta por conta própria. Para [10, 4, 1], você remove 10 e 4 e insere 6; depois remove 6 e 1 e insere 5, e o heap fica apenas com 5.

Há no máximo n-1 rodadas, cada uma com duas remoções e no máximo uma inserção, então o tempo é O(n log n) e o heap usa O(n) de espaço. Algumas linguagens já incluem um heap: o heapq do Python é um min-heap, então armazena pesos negados; Java tem PriorityQueue, C++ tem priority_queue, Go tem container/heap, Rust tem BinaryHeap e PHP tem SplMaxHeap. Nas outras linguagens, a solução implementa seu próprio heap em um array: o pai do índice i fica em (i-1)/2, e um novo valor sobe enquanto for maior que o pai.

Algoritmo

Coloque todas as pedras em um heap máximo.
Enquanto o heap contiver mais de uma pedra, remova a mais pesada e depois a segunda mais pesada.
Se forem diferentes, insira heaviest - second.
Retorne o elemento do topo do heap ou 0 quando ele estiver vazio.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Armadilhas e casos extremos

A simulação é curta, então os bugs se escondem nas extremidades e na própria heap.

Retornar o topo de uma pilha vazia. Quando as duas últimas pedras têm o mesmo peso, não sobra nada, e a resposta é 0.
Usar acidentalmente uma min-heap. O heapq do Python e o PriorityQueue padrão do Java fornecem o menor valor; negue os pesos ou passe um comparador reverso.
Esquecer de negar de volta. Com heapq, os dois valores removidos são negativos, então a diferença que você insere é -(heaviest - second).
Ordenar uma vez no início e percorrer a lista. A diferença entre duas pedras pode ser menor do que o peso de pedras que você ainda não tocou, então uma ordem fixa fica desatualizada após a primeira rodada.

Perguntas frequentes4

Qual é a complexidade de tempo de Last Stone Weight?

Com um max-heap, construir o heap e jogar no máximo n-1 rodadas, com duas remoções e uma inserção cada, leva tempo O(n log n) e espaço O(n). Ordenar a pilha inteira a cada rodada, em vez disso, leva O(n² log n).

Por que usar um heap para Last Stone Weight?

A cada rodada, é preciso encontrar os dois maiores valores de uma coleção que muda após cada rodada. Um heap responde à pergunta “qual é o maior” e aceita um novo valor em O(log n), sem manter a coleção inteira ordenada. Esse é exatamente o trabalho que a simulação repete.

É possível resolver Last Stone Weight sem uma heap?

Sim, porque os pesos são pequenos. Conte quantas pedras há de cada peso, de 1 a 1000, e percorra os pesos do mais pesado ao mais leve. Pedras iguais se cancelam aos pares, e uma pedra nova é sempre mais leve do que a pedra mais pesada usada para criá-la, então o percurso só segue para baixo. Isso leva O(n + W) tempo para o maior peso W.

A ordem em que pedras de mesmo peso são esmagadas muda a resposta?

Não. Quando várias pedras têm o mesmo peso máximo, as duas que você escolher terão o mesmo peso de qualquer forma, então a pilha após a rodada terá os mesmos pesos. A resposta depende apenas dos pesos, por isso toda solução correta retorna o mesmo número.

Python

def lastStoneWeight(stones):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

stones = [3, 9, 4, 6, 2]

Esperado