Pular para o conteúdo

Esmagar as pedras mais pesadas

Fácil#max-heap#simulation~20 min

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

Tempo-alvo
O(n log n)
Espaço-alvo
O(n)

Travou na ideia, e não no código? O básico de heaps explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado