解法一:大根堆
维护一个大根堆即可。每次取出两个重量最大的石头模拟题目所述操作。
import java.util.PriorityQueue;
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int i : stones) {
queue.offer(i);
}
int w1, w2;
while (queue.size() >= 2) {
w1 = queue.poll();
w2 = queue.poll();
if (w1 > w2) {
queue.offer(w1 - w2);
}
}
if (queue.isEmpty()) {
return 0;
} else {
return queue.poll();
}
}
}