# Leetcode: Last Stone Weight

Last Stone Weight

Similar Problems:

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose the two heaviest rocks 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.)

Example 1:

```Input: [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
```

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/last-stone-weight
// Basic Idea: heap
// Complexity: Time O(n*log(n)), Space O(n)
import (
"container/heap"
"fmt"
)

// An IntHeap is a max-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}

func lastStoneWeight(stones []int) int {
h := &IntHeap{}
heap.Init(h)
for _, val := range stones {
heap.Push(h, val)
}

for h.Len() > 1 {
v1, _ := heap.Pop(h).(int)
v2, _ := heap.Pop(h).(int)
heap.Push(h, v1-v2)
}

res, _ := heap.Pop(h).(int)
return res
}
```

Share It, If You Like It.