Description
Given an array nums, you can decrease any element. Minimize the maximum value of the array. Return the minimum possible maximum.
Examples
Input:
nums = [3,7,1,6]Output:
5Explanation:
Optimal redistribution.
Input:
nums = [1,2,3,4,5]Output:
3Explanation:
The sum is 15, so the minimum possible maximum is 15/5 = 3. Since it is possible to redistribute values from right to left (larger indices can give to smaller indices), it is possible to achieve this ideal average. The optimal distribution would be [3,3,3,3,3].
Input:
nums = [9,1,1]Output:
4Explanation:
The sum is 11, and 11/3 ≈ 3.67, but since the requirement is integers, checking if 4 is achievable. It is possible to redistribute to get [4,3,4] or [4,4,3] by moving 1 unit from index 0 to index 1, resulting in a maximum value of 4.
Constraints
- •
1 ≤ n ≤ 10⁵