Esmagar as pedras mais pesadas
A missão
Problema
Uma pilha de pedras é descrita pelos seus pesos. Repetidamente, pegue as duas pedras mais pesadas e esmague uma contra a outra: pedras iguais se destroem por completo, enquanto pedras diferentes deixam uma única pedra com o peso da diferença, que volta para a pilha. Retorne o peso da última pedra que sobrar, ou 0 quando a pilha esvaziar.
Exemplos
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Por quê: 7 e 8 deixam 1, depois 2 e 4 deixam 2, depois 1 e 2 deixam 1, e por fim 1 e 1 somem
Input: stones = [1, 1]
Output: 0
Por quê: duas pedras iguais se destroem e não sobra nada
Input: stones = [3]
Output: 3
Por quê: edge case: uma pedra sozinha não tem contra o que ser esmagada
Dicas
0 / 3
Ordenar a pilha inteira de novo depois de cada choque é correto, mas faz muito mais trabalho do que a pergunta exige, já que só duas pedras mudam a cada rodada.
A única coisa que você pede à pilha é “me dê a mais pesada agora”, e a única coisa que volta para ela é uma única pedra nova. Esse par de operações dá nome à estrutura.
Carregue todos os pesos em uma estrutura que sempre devolve o maior item e aceita itens novos a baixo custo. Em cada rodada, retire dois itens e devolva a diferença só quando ela não for zero. Pare quando restarem menos de dois itens.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Solução
Só duas perguntas são feitas à pilha, “me dê a mais pesada” e “guarde esta pedra nova”, e é exatamente isso que um heap responde em tempo logarítmico. Montar o heap uma vez e depois esmagar repetidamente evita ordenar de novo a cada rodada. Uma diferença zero simplesmente não volta para o heap, então a pilha diminui em duas pedras nesse caso e em uma nos outros, e o loop termina com uma pedra ou com nenhuma. O tempo é O(n log n), e o espaço é O(n) para o heap.
import heapq
def last_stone_weight(stones):
heap = [-w for w in stones] # negated, because the library heap is a min-heap
heapq.heapify(heap)
while len(heap) > 1:
heaviest = -heapq.heappop(heap)
second = -heapq.heappop(heap)
if heaviest != second: # equal stones vanish, so nothing goes back
heapq.heappush(heap, -(heaviest - second))
return -heap[0] if heap else 0
print(last_stone_weight([2, 7, 4, 1, 8, 1])) # -> 1
print(last_stone_weight([1, 1])) # -> 0
print(last_stone_weight([3])) # -> 3Travou na ideia, e não no código? O básico de heaps explica isso.