Задача: 1046. Last Stone Weight
Сложность: easy

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

👨‍💻 Алгоритм:

1⃣Создай максимальную кучу из массива камней.

2⃣Извлекай два самых тяжелых камня, разбивай их, и, если необходимо, возвращай оставшийся камень обратно в кучу.

3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось.

😎 Решение:

import java.util.Collections;
import java.util.PriorityQueue;

public class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones) {
            maxHeap.add(stone);
        }
        
        while (maxHeap.size() > 1) {
            int first = maxHeap.poll();
            int second = maxHeap.poll();
            if (first != second) {
                maxHeap.add(first - second);
            }
        }
        
        return maxHeap.isEmpty() ? 0 : maxHeap.poll();
    }
}

Ставь 👍 и забирай 📚 Базу знаний