How do you solve the last stone weight problem, and what does the problem really ask?
You keep the two heaviest stones in a heap, you smash them together, and you put back whatever is left. You keep going until there is one stone or none at all.
So what does the problem really ask? It asks for the weight of the last stone, or zero if there is nothing left. And the interesting part is what "smashing" means. Two stones of weight a and b are put together. If they are the same weight then they both break and nothing is left. If they are different then the heavier one loses the difference, so the stone that goes back has the weight of the bigger one minus the smaller one.
the two stones the result
---------------- -----------------------
7 and 4 a stone of 3
7 and 7 nothing at all
And why do you need a heap? Because you always need the two heaviest stones, and the heap gives you the biggest one in constant time. Taking the biggest one out and then taking the next biggest one out gives you the pair you need.
And there is a detail worth knowing about. You cannot use a min heap directly, because you want the biggest stones and a min heap gives you the smallest. So you store the weights turned round, and then the smallest stored value is the biggest real weight.
import heapq
heap = [-7, -4, -3]
heapq.heapify(heap)
print(-heap[0]) # 7, the biggest real weight
And the complexity is O of n log n for the time, because each round takes two stones out and puts at most one back, so there are O of n rounds and each one costs O of log n. And the space is O of n.
So the rule to remember is this. The answer is the weight of the last stone, and you need a max heap to find the two heaviest quickly.
The last question in this topic shows the code.