Last Stone Weight

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

Com um heap máximo, no máximo n-1 rodadas de duas remoções e uma inserção levam O(n log n) de tempo e O(n) de espaço. Ordenar a pilha inteira a cada rodada 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 uma contra a outra. Se elas tiverem o mesmo peso, ambas serão destruídas. Caso contrário, a mais leve será destruída e a mais pesada ficará com o peso equivalente à diferença entre os dois pesos.

Escreva lastStoneWeight, que joga rodadas até restar no máximo uma pedra e retorna seu peso, 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 1 se destroem, então a resposta é 0.

Entrada: stones = [10, 4, 1]
Saída: 5
Explicação: 10 e 4 deixam 6, e 6 e 1 deixam 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.

Para ir além

Os pesos são, no máximo, 1000. Você consegue usar esse limite para concluir em tempo O(n + W), 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

Não existe uma fórmula para pular etapas: você joga todas as rodadas. Cada rodada precisa das duas pedras mais pesadas de uma pilha que está sempre mudando, porque uma pedra quebrada pode voltar mais leve. Um heap máximo fornece a pedra mais pesada e recebe uma nova em O(log n).

Classifique a pilha a cada rodada

Correta, mas não termina nos maiores testes

Intuição

Siga as regras literalmente: ordene a pilha, pegue as duas pedras mais pesadas do final e coloque a diferença de volta se ela não for zero. Ordene novamente a cada rodada, porque a diferença pode ficar em qualquer posição. No primeiro exemplo, 9 e 6 deixam uma 3, que deve ficar abaixo da 4.

Cada rodada remove pelo menos uma pedra, então há até n-1 rodadas, cada uma ordenando até n pedras: O(n² log n). Para n = 10^4, isso dá cerca de 10^4 ordenações de até 10^4 números.

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

Heap máximo

Intuição

Um heap máximo mantém o maior valor no topo, e remover o elemento do topo ou adicionar um valor custa O(log n). Coloque cada pedra nele. A cada rodada, remova os dois elementos do topo, que são os mais pesados, e insira novamente a diferença se ela não for zero; o heap a posiciona corretamente. Para [10, 4, 1], remova 10 e 4 e insira 6; depois, remova 6 e 1 e insira 5.

Há no máximo n-1 rodadas, cada uma com duas remoções e uma inserção, então o tempo é O(n log n) e o espaço é O(n). Em linguagens sem um heap integrado, a solução mantém um em um array, com o pai do índice i no índice (i-1)/2.

Algoritmo

Coloque cada pedra em uma max-heap.
Enquanto a heap tiver mais de uma pedra, remova a mais pesada e depois a segunda mais pesada.
Se forem diferentes, insira heaviest - second.
Retorne o topo da heap ou 0 quando ela estiver vazia.

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

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

Perguntas frequentes3

Qual é a complexidade de tempo de Last Stone Weight?

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

Por que usar um heap para Last Stone Weight em vez de uma lista ordenada?

Uma lista ordenada fornece de uma vez as duas pedras mais pesadas, mas reinserir a diferença na ordem desloca até n entradas, O(n²) ao longo de todas as rodadas. Um heap só responde “qual é o maior” e aceita um novo valor, ambos em O(log n), que é tudo o que a simulação exige.

A ordem em que pedras de pesos iguais 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 maneira, então a pilha após a rodada terá os mesmos pesos. A resposta depende apenas dos pesos.

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada