最小化数组中的最大值

leetCode2439-最小化数组中的最大值

示例 1：

输入：nums = [3,7,1,6]
输出：5
解释：
一串最优操作是：

1. 选择 i = 1 ，nums 变为 [4,6,1,6] 。
2. 选择 i = 3 ，nums 变为 [4,6,2,5] 。
3. 选择 i = 1 ，nums 变为 [5,5,2,5] 。
   nums 中最大值为 5 。无法得到比 5 更小的最大值。
   所以我们返回 5 。

示例 2：

输入：nums = [10,1]
输出：10
解释：
最优解是不改动 nums ，10 是最大值，所以返回 10 。

+++++++++++++

方法1

思路：最小化最大值问题=二分法

从后向前模拟。

代码为：

class Solution {
    public int minimizeArrayValue(int[] nums) {
        int l = Arrays.stream(nums).min().getAsInt();
        int r = Arrays.stream(nums).max().getAsInt();
        while (l<r){
            int mid = (l+r)>>1;
            if(check(nums,mid)<=mid){
                r = mid;
            }else {
                l = mid+1;
            }
        }
        return l;
    }
    //从后向前模拟
    public static long check(int nums[],int n){
        long arr[] = new long[nums.length];
        for (int i = 0;i<nums.length;i++){
            arr[i] =(long) nums[i];
        }
        for (int i = arr.length-1;i>0;i--){
            if (arr[i]>=n){
                long t = arr[i]-n;
                arr[i-1]+= t;
                arr[i] = n;
            }
        }
        return arr[0];
    }
}

方法2