1046.last-stone-weight.md

1046. Last Stone Weight

Heap

fun lastStoneWeight(stones: IntArray): Int {
    val maxHeap = PriorityQueue(reverseOrder<Int>())
    for (stone in stones) maxHeap.add(stone)

    while (maxHeap.isNotEmpty()) {
        val first = maxHeap.poll()
        if (maxHeap.isEmpty()) return first
        val second = maxHeap.poll()

        if (first != second) maxHeap.add(abs(first - second))
    }
    return 0
}

• Time Complexity: O(n lg n), comparsion take n - 1 times and every time take lg n to poll the largest two stones.
• Space Complexity: O(n).