1046. Last Stone Weight

Easy

Description

有一堆石頭，每塊石頭有正整數重量。每回合選出最重的兩塊石頭互相碰撞：若兩塊一樣重，都消失；若不同，較輕的消失，較重的變成差值。最後剩下的石頭重量是多少？若沒有剩餘則回傳 0。

Example:

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

Intuition#

核心思路：每次都要取最大的兩個元素，Max Heap 是天然的選擇。

每回合需要最重的兩塊石頭 → 需要高效取最大值的資料結構
Max Heap 可以 O(1) 取最大值，O(log n) 插入和刪除
模擬碰撞過程，直到剩下 0 或 1 塊石頭

Approaches#

1: Sorting Each Round#

概念: 每回合排序陣列，取最後兩個元素碰撞，將結果放回陣列
時間複雜度: O(n^2 log n) - 最多 n 回合，每回合排序 O(n log n)
空間複雜度: O(n)

class Solution {
    fun lastStoneWeight(stones: IntArray): Int {
        val list = stones.toMutableList()
        while (list.size > 1) {
            list.sort()
            val first = list.removeAt(list.lastIndex)
            val second = list.removeAt(list.lastIndex)
            if (first != second) {
                list.add(first - second)
            }
        }
        return if (list.isEmpty()) 0 else list[0]
    }
}

⭐2: Max Heap#

概念: 用 Max Heap 存所有石頭，每回合取出最大的兩塊碰撞，若有剩餘則放回 heap
時間複雜度: O(n log n) - 最多 n 回合，每回合 heap 操作 O(log n)
空間複雜度: O(n)

class Solution {
    fun lastStoneWeight(stones: IntArray): Int {
        val maxHeap = PriorityQueue<Int>(compareByDescending { it })
        for (s in stones) maxHeap.offer(s)

        while (maxHeap.size > 1) {
            val first = maxHeap.poll()
            val second = maxHeap.poll()
            if (first != second) {
                maxHeap.offer(first - second)
            }
        }

        return if (maxHeap.isEmpty()) 0 else maxHeap.peek()
    }
}

🔑 Takeaways#

Pattern: 反覆取最大/最小值的模擬題，用 Heap 來加速
關鍵技巧: Kotlin/Java 的 PriorityQueue 預設是 Min Heap，要 Max Heap 需傳入 compareByDescending { it } 或 reverseOrder()