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 weightx
is totally destroyed, and the stone of weighty
has new weighty-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 <= stones.length <= 30
1 <= stones[i] <= 1000
Solution
Use
Priority queue (heap)
to simulate the process.
class Solution {
func lastStoneWeight(_ stones: [Int]) -> Int {
var heap = Heap<Int>(elements: stones, priorityFunction: >) // O(n)
while heap.count > 1 {
let first = heap.dequeue()! // O(logn) time
let second = heap.dequeue()! // O(logn) time
let newVal = abs(first - second)
if newVal > 0 {
heap.enqueue(newVal)
}
}
if heap.count == 0 { return 0 }
return heap.peek()!
}
}
Detail about how to implement Priority Queue
can be found here