給定一個非負整數陣列
nums。每次操作可以選擇一個索引i > 0，將nums[i]減 1 同時將nums[i-1]加 1。回傳能使陣列最大值最小化的結果。
Example:
Input: nums = [3,7,1,6] Output: 5
Intuition
TIP
操作只能把值往左移，所以前 k 個元素的平均值是前 k 個最大值的下界。
- 操作本質是將值從右往左搬移
- 對於前
k個元素，無論怎麼搬，最大值不可能低於它們的平均值（向上取整） - 答案就是所有前綴平均值（向上取整）的最大值
Approaches
1. Binary Search — O(n log M) / O(1)
- Idea: 二分答案
mid，檢查是否能讓所有元素不超過mid。貪心地將多出的值往左搬。 - Time:
O(n log M)，M 為最大值 - Space:
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. Prefix Sum + Greedy — O(n) / O(1)
- Idea: 答案 = max(ceil(prefixSum[k] / k))，即所有前綴平均值的最大值向上取整。
- Time:
O(n) - Space:
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: 前綴和 + 貪心 — 操作只能往左搬，前綴平均值是下界
- Key trick: 向上取整公式
ceil(a/b) = (a + b - 1) / b；理解「值只能左移」的性質是關鍵