Saltar al contenido

Choque de las piedras más pesadas

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

La misión

Problema

Un montón de piedras se describe por sus pesos. Toma repetidamente las dos piedras más pesadas y hazlas chocar: dos piedras iguales se destruyen por completo, mientras que dos distintas dejan una sola piedra cuyo peso es la diferencia, y esa piedra vuelve al montón. Devuelve el peso de la última piedra que quede, o 0 si el montón se vacía.

Ejemplos

Input:  stones = [2, 7, 4, 1, 8, 1]
Output: 1
Por qué: 7 y 8 dejan 1, luego 2 y 4 dejan 2, luego 1 y 2 dejan 1, y por último 1 y 1 desaparecen
Input:  stones = [1, 1]
Output: 0
Por qué: dos piedras iguales se destruyen entre sí y no queda nada
Input:  stones = [3]
Output: 3
Por qué: caso límite: una piedra sola no tiene contra qué chocar

Pistas

0 / 3

Tiempo objetivo
O(n log n)
Espacio objetivo
O(n)

¿Lo que te frena es la idea y no el código? Fundamentos del heap lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio