2439.Minimize Maximum of Array === ###### tags: `Medium`,`Array`,`Binary Search`,`Greedy`,`DP`,`Prefix Sum` [2439. Minimize Maximum of Array](https://leetcode.com/problems/minimize-maximum-of-array/) ### 題目描述 You are given a **0-indexed** array `nums` comprising of `n` non-negative integers. In one operation, you must: * Choose an integer `i` such that `1 <= i < n` and `nums[i] > 0`. * Decrease `nums[i]` by 1. * Increase `nums[i - 1]` by 1. Return *the **minimum** possible value of the **maximum** integer of* `nums` *after performing **any** number of operations.* ### 範例 **Example 1:** ``` Input: nums = [3,7,1,6] Output: 5 Explanation: One set of optimal operations is as follows: 1. Choose i = 1, and nums becomes [4,6,1,6]. 2. Choose i = 3, and nums becomes [4,6,2,5]. 3. Choose i = 1, and nums becomes [5,5,2,5]. The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5. Therefore, we return 5. ``` **Example 2:** ``` Input: nums = [10,1] Output: 10 Explanation: It is optimal to leave nums as is, and since 10 is the maximum value, we return 10. ``` **Constraints**: * `n` == `nums.length` * 2 <= `n` <= 10^5^ * 0 <= `nums[i]` <= 10^9^ ### 解答 #### C++ ```cpp= class Solution { public: int minimizeArrayValue(vector<int>& nums) { long long ans = 0, sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; ans = max(ans, (sum + i) / (i + 1)); } return ans; } }; ``` > [name=Yen-Chi Chen][time=Wed, Apr 5, 2023] #### Python ```python= class Solution: def minimizeArrayValue(self, nums: List[int]) -> int: ans, total = 0, 0 for i, num in enumerate(nums): total += num ans = max(ans, (total + i) // (i + 1)) return ans ``` > [name=Yen-Chi Chen][time=Wed, Apr 5, 2023] #### Javascript ```javascript= function minimizeArrayValue(nums) { let min = nums[0]; let max = Math.max(...nums); while (max > min) { const mid = Math.floor((max + min) / 2); let sum = 0; for (const num of nums) { sum += mid - num; if (sum < 0) break; } if (sum < 0) { min = mid + 1; } else { max = mid; } } return min; } ``` > binary search版本 > [name=Marsgoat][time=Apr 11, 2023] ```javascript= function minimizeArrayValue(nums) { let result = 0; let sum = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i]; result = Math.max(result, Math.ceil(sum / (i + 1))); } return result; } ``` > 跟吉神學習了,真的好神... > [name=Marsgoat][time=Apr 11, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)