Choque de las piedras más pesadas
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
Volver a ordenar todo el montón después de cada choque es correcto, pero hace mucho más trabajo del necesario, ya que en cada ronda solo cambian dos piedras.
Lo único que se le pide al montón es “dame la más pesada ahora”, y lo único que se le devuelve es una sola piedra nueva. Ese par de operaciones te dice qué estructura usar.
Carga todos los pesos en una estructura que siempre te entregue el elemento más grande y acepte elementos nuevos a bajo costo. En cada ronda, toma dos elementos y vuelve a poner su diferencia solo cuando no sea cero. Detente cuando queden menos de dos elementos.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Solución
Al montón solo se le hacen dos pedidos, “dame la más pesada” y “toma esta piedra nueva”, que es exactamente lo que un heap (montículo) resuelve en tiempo logarítmico. Construirlo una vez y luego hacer chocar las piedras una y otra vez evita volver a ordenar después de cada ronda. Una diferencia de cero simplemente no se vuelve a insertar, así que en ese caso el montón se reduce en dos piedras y, en los demás, en una, y el bucle termina con una piedra o con ninguna. El tiempo es O(n log n) y el espacio es O(n) para el 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])) # -> 3¿Lo que te frena es la idea y no el código? Fundamentos del heap lo explica.