Условие

Дан массив камней stones, где stones[i] — вес i-го камня.

Игра:

• Выбираются два самых тяжелых камня x и y (x <= y).

• Если x == y, оба уничтожаются.

• Если x < y, остается камень весом y - x.

• Повторять, пока не останется 0 или 1 камень.

Верните вес оставшегося камня или 0, если камней нет.

Примеры

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

Мы объединяем 7 и 8, получаем 1, поэтому массив превращается в [2,4,1,1,1], затем, мы объединяем 2 и 4, получаем 2, поэтому массив превращается в [2,1,1,1], затем, мы объединяем 2 и 1, получаем 1, поэтому массив превращается в [1,1,1], затем, мы объединяем 1 и 1, получаем 0, поэтому массив превращается в [1], и это значение последнего камня.

Input: stones = [1] Output: 1

Решение

fun lastStoneWeight(stones: IntArray): Int {
    // Используем максимальную кучу (PriorityQueue с обратным порядком)
    val maxHeap = PriorityQueue<Int>(compareByDescending { it })
    
    // Заполняем кучу начальными значениями
    stones.forEach { maxHeap.add(it) }

    // Пока в куче больше одного камня, выполняем бой
    while (maxHeap.size > 1) {
        val y = maxHeap.poll() // Самый тяжелый камень
        val x = maxHeap.poll() // Второй по тяжести камень

        // Если после столкновения остается камень, добавляем его обратно в кучу
        if (x != y) maxHeap.add(y - x)
    }

    // Если остался один камень, возвращаем его вес, иначе 0
    return maxHeap.poll() ?: 0
}

Временная сложность

O(n log n), так как используем кучу для операций извлечения и вставки.