Minimize Array Maximum
MediumGreedy · Snowflake
You are given an array of non-negative integers nums. In one operation you choose an index i with i > 0 and nums[i] > 0, then decrease nums[i] by 1 and increase nums[i - 1] by 1. In other words, a unit can move one step to the left.
You may perform any number of operations, including none. Return the smallest possible value of the maximum element of nums.
Example 1
- Input:
- nums = [1, 5, 7, 6]
- Output:
- 5
- Explanation
- The first three values total 13. Units can move left but never right, so those three slots always share at least 13, and one of them must hold at least
ceil(13 / 3) = 5. Spreading to[5, 4, 4, 6]and then[5, 5, 4, 5]reaches 5.
Example 2
- Input:
- nums = [5, 15, 19]
- Output:
- 13
- Explanation
- The total is 39 over 3 slots, so the maximum is at least 13, and moving units left gives
[13, 13, 13].
Example 3
- Input:
- nums = [10, 3, 5, 7]
- Output:
- 10
- Explanation
- Nothing can move into index 0 from its left or out of it, so
10stays, and the rest can be levelled below it.
Constraints
- 1 ≤
nums.length≤ 105 - 0 ≤
nums[i]≤ 109