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
- 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:
Note:
1 <= stones.length <= 30 1 <= stones[i] <= 1000
Solution
Every time to pick highest weight stones, We can use priority queue which can order stones based on their weight, Every time peek two stones and add difference back to queue.
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.PriorityQueue; public class LastStoneWeight { public int lastStoneWeight(int[] stones) { PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); for (int stone : stones) { pq.offer(stone); } for (int i = 0; i < stones.length - 1; i++) { pq.offer(pq.poll() - pq.poll()); } return pq.poll(); } public static void main(String[] args) { int [] a= {2,7,4,1,8,1}; System.out.println(new LastStoneWeight().lastStoneWeight(a)); } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.