給定一個正整數陣列
nums，你可以對任意元素執行以下操作任意次：若元素為偶數，可以除以 2；若元素為奇數，可以乘以 2。求陣列中最大值與最小值之差（deviation）的最小可能值。
Example:
Input: nums = [1,2,3,4] Output: 1
Intuition
TIP
核心思路：先把所有數都變成最大值（奇數乘 2），然後用 Max Heap 不斷縮小最大值，追蹤最小 deviation。
- 奇數只能乘以 2 一次（變偶數），偶數可以一直除以 2 直到變奇數
- 統一策略：先把所有奇數乘 2（變成各自的最大可能值），這樣每個數只能往下縮
- 用 Max Heap 追蹤當前最大值，同時記錄全域最小值
- 每次把最大值除以 2（只有偶數才能除），更新 deviation，直到最大值為奇數時停止
Approaches
1. TreeSet (min & max together) — O(n · log(maxVal) · log n) / O(n)
- Idea: 與堆解同邏輯，改用
TreeSet一個結構同時 O(log n) 取最大與最小，程式更簡潔 - Time:
O(n · log(maxVal) · log n) - Space:
O(n)
class Solution {
fun minimumDeviation(nums: IntArray): Int {
val set = java.util.TreeSet<Int>()
for (x in nums) set.add(if (x % 2 == 1) x * 2 else x) // 奇數先 *2
var res = set.last() - set.first()
while (set.last() % 2 == 0) { // 最大是偶數才能再 /2 變小
val max = set.pollLast()
set.add(max / 2)
res = minOf(res, set.last() - set.first())
}
return res
}
}⭐ 2. Max Heap + Greedy — O(n * log(maxVal) * log n) / O(n)
- Idea: 將所有奇數先乘 2 推入 Max Heap，追蹤最小值。每次取出最大值，若為偶數則除以 2 後放回，更新 deviation
- Time:
O(n * log(maxVal) * log n)- 每個元素最多被除 log(maxVal) 次，每次 heap 操作 O(log n) - Space:
O(n)
class Solution {
fun minimumDeviation(nums: IntArray): Int {
val maxHeap = PriorityQueue<Int>(compareByDescending { it })
var minVal = Int.MAX_VALUE
for (num in nums) {
val val_ = if (num % 2 == 1) num * 2 else num
maxHeap.offer(val_)
minVal = minOf(minVal, val_)
}
var result = maxHeap.peek() - minVal
while (maxHeap.peek() % 2 == 0) {
val maxVal = maxHeap.poll()
val halved = maxVal / 2
maxHeap.offer(halved)
minVal = minOf(minVal, halved)
result = minOf(result, maxHeap.peek() - minVal)
}
return result
}
}🔑 Takeaways
- Pattern: 先統一方向（全部拉到最大），再用 Heap 貪心地逐步縮小範圍
- Key trick: 奇偶操作的不對稱性——先把奇數乘 2 統一成偶數，讓所有數都只能往下除；Max Heap 頂部偶數才能繼續除，奇數到頂時即為終止條件