2439. Minimize Maximum of Array

Minimize Maximum of Array

題目描述： 給定一個整數陣列 nums，每步操作可以選擇一個索引 i > 0，將 nums[i] 減 1 同時 nums[i-1] 加 1（即將值向左移動）。可以執行任意次操作，求陣列中最大值的最小可能值。

解題思路： 操作的本質是將值從右往左搬移。因此對於任意前綴 nums[0..i]，其總和不會改變（只能從右往左搬，前綴和只增不減）。前 i+1 個元素的最大值至少為 ceil(prefix_sum[i+1] / (i+1))。

答案即為所有前綴的平均值上整的最大值： ans = max over i in [0, n-1] of ceil(sum(nums[0..i]) / (i+1))

直觀理解：每個前綴的值只能在其內部重新分配（右邊的值可以移到左邊），最優分配是盡可能平均。

時間複雜度：O(n) — 單次遍歷陣列。

空間複雜度：O(1) — 只使用常數額外空間。

二分搜尋 O(n log M)：二分答案 mid，對每個候選值檢查是否可以通過操作使所有元素 <= mid。驗證時從左到右貪心：若 nums[i] < mid 則「容量」可以吸收右邊多餘的值。時間複雜度較高但思路直觀。

模擬法 O(n * max)：直接模擬操作過程，每次找到最大值並向左移動。時間複雜度過高，不可行。

1. 如果操作方向改為「只能向右搬移」（nums[i] 減 1，nums[i+1] 加 1），答案如何變化？
2. 如果每步操作可以向左或向右搬移，問題變簡單還是更難？
3. 如何證明前綴平均值上整的最大值就是最終答案？