1675. Minimize Deviation in Array

Hard

Description

給定一個正整數陣列 nums，你可以對任意元素執行以下操作任意次：若元素為偶數，可以除以 2；若元素為奇數，可以乘以 2。求陣列中最大值與最小值之差（deviation）的最小可能值。

Example:

Input: nums = [1,2,3,4] Output: 1

Intuition#

核心思路：先把所有數都變成最大值（奇數乘 2），然後用 Max Heap 不斷縮小最大值，追蹤最小 deviation。

奇數只能乘以 2 一次（變偶數），偶數可以一直除以 2 直到變奇數
統一策略：先把所有奇數乘 2（變成各自的最大可能值），這樣每個數只能往下縮
用 Max Heap 追蹤當前最大值，同時記錄全域最小值
每次把最大值除以 2（只有偶數才能除），更新 deviation，直到最大值為奇數時停止

Approaches#

⭐1: Max Heap + Greedy#

概念: 將所有奇數先乘 2 推入 Max Heap，追蹤最小值。每次取出最大值，若為偶數則除以 2 後放回，更新 deviation
時間複雜度: O(n * log(maxVal) * log n) - 每個元素最多被除 log(maxVal) 次，每次 heap 操作 O(log n)
空間複雜度: 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 貪心地逐步縮小範圍
關鍵技巧: 奇偶操作的不對稱性——先把奇數乘 2 統一成偶數，讓所有數都只能往下除；Max Heap 頂部偶數才能繼續除，奇數到頂時即為終止條件