2439. Minimize Maximum of Array

Medium

Description

給定一個非負整數陣列 nums。每次操作可以選擇一個索引 i > 0，將 nums[i] 減 1 同時將 nums[i-1] 加 1。回傳能使陣列最大值最小化的結果。

Example:

Input: nums = [3,7,1,6] Output: 5

Intuition#

操作只能把值往左移，所以前 k 個元素的平均值是前 k 個最大值的下界。

操作本質是將值從右往左搬移
對於前 k 個元素，無論怎麼搬，最大值不可能低於它們的平均值（向上取整）
答案就是所有前綴平均值（向上取整）的最大值

Approaches#

1: 二分搜尋#

概念: 二分答案 mid，檢查是否能讓所有元素不超過 mid。貪心地將多出的值往左搬。
時間複雜度: O(n log M)，M 為最大值
空間複雜度: O(1)

class Solution {
    fun minimizeArrayValue(nums: IntArray): Int {
        var lo = 0
        var hi = nums.max()

        while (lo < hi) {
            val mid = lo + (hi - lo) / 2
            var excess = 0L
            var feasible = true
            for (i in nums.indices.reversed()) {
                val diff = nums[i].toLong() - mid + excess
                excess = if (diff > 0) diff else 0
            }
            if (excess == 0L) hi = mid else lo = mid + 1
        }
        return lo
    }
}

⭐2: 前綴和貪心#

概念: 答案 = max(ceil(prefixSum[k] / k))，即所有前綴平均值的最大值向上取整。
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun minimizeArrayValue(nums: IntArray): Int {
        var result = 0L
        var prefixSum = 0L

        for (i in nums.indices) {
            prefixSum += nums[i]
            // 前 i+1 個元素的平均值向上取整
            result = maxOf(result, (prefixSum + i) / (i + 1))
        }
        return result.toInt()
    }
}

🔑 Takeaways#

Pattern: 前綴和 + 貪心 — 操作只能往左搬，前綴平均值是下界
關鍵技巧: 向上取整公式 ceil(a/b) = (a + b - 1) / b；理解「值只能左移」的性質是關鍵