We have a collection of stones, each stone has a positive integer weight.
Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)
Solution
Brute force solution
There is a solution with O(N^2*LogN) time complexity. Which is you try to sort the array, pick two largest and do the math. You will need to repeat this process until you get array with 0 or 1 element.
Better solution
For the brute force solution, the most time-consuming part is sorting the array to get two largest elements. We may to optimize this by using heap.
The idea of heap (in this case, we will use binary heap) is that heap is a completed binary tree and all node will have value larger than its children nodes value.
So with heap, we can transform the given input array into a heap. We try to pop 2 value out from the heap each time, do the math and insert new stone into the heap if necessary. We will repeat this process until heap has only 0 or 1 element.
// Heap must not be empty func (h *heap) Pop() int { curLen := h.Size() res := h.number[0] h.number[0] = h.number[curLen-1] h.number = h.number[:curLen-1] h.Downheap(0) return res }