有一堆石頭，每塊石頭有正整數重量。每回合選出最重的兩塊石頭互相碰撞：若兩塊一樣重，都消失；若不同，較輕的消失，較重的變成差值。最後剩下的石頭重量是多少？若沒有剩餘則回傳 0。
Example:
Input: stones = [2,7,4,1,8,1] Output: 1
Intuition
TIP
核心思路：每次都要取最大的兩個元素，Max Heap 是天然的選擇。
- 每回合需要最重的兩塊石頭 → 需要高效取最大值的資料結構
- Max Heap 可以 O(1) 取最大值，O(log n) 插入和刪除
- 模擬碰撞過程，直到剩下 0 或 1 塊石頭
Approaches
1. Sorting Each Round — O(n^2 log n) / O(n)
- Idea: 每回合排序陣列，取最後兩個元素碰撞，將結果放回陣列
- Time:
O(n^2 log n)- 最多 n 回合，每回合排序 O(n log n) - Space:
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 — O(n log n) / O(n)
- Idea: 用 Max Heap 存所有石頭，每回合取出最大的兩塊碰撞，若有剩餘則放回 heap
- Time:
O(n log n)- 最多 n 回合，每回合 heap 操作 O(log n) - Space:
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 來加速
- Key trick: Kotlin/Java 的 PriorityQueue 預設是 Min Heap，要 Max Heap 需傳入
compareByDescending { it }或reverseOrder()