[leetcode] problem 1046 – last stone weight

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

Note

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public int (int[] stones) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
        
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    for (int stone : stones)
        pq.offer(stone);

    while (pq.size() > 1) {
        int x = pq.poll();
        int y = pq.poll();

        if (x != y)
            pq.offer(x - y);
    }

    return pq.isEmpty() ? 0 : pq.poll();
}