题目分析

本题是第89场周赛的第三题，之前有提到过，见到最大值最小、最小值最大，我们应该首先想到二分查找，小伙伴们能否用二分查找求出本题？

二分查找

直到使用二分查找，剩下的就是确定left和right，其中最大值的下限肯定是整个数组的均值向上求和，最大值的上限肯定是整个数组的最大值。

确定了二分查找的边界，下面就是判断函数如何写，即给定一个值，如何确定该值是否满足条件？

假如给定k，即令最大值最小为k。我们发现本题是相当于右边的元素向左边平均，那么最左边的元素一定不能大于k，因为该元素无法变小，使其小于等于k。

而且最左边的元素要尽量移动到k，这样右边的元素才会越小，所以可以从左向右移动，如果某一位大于k，则直接return false，否则可以将其补到k，然后让右边的元素变小。

当元素k成立后，我们就可以让right变为k继续二分，如果k不成立，那么让left变为k + 1继续二分。当left >= right的时候，说明找到了k。

所以算法的时间复杂度为O(nlog(n))，空间复杂度为O(n)。

class Solution {
    public int minimizeArrayValue(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int left = sum / nums.length;
        int right = Arrays.stream(nums).max().getAsInt();
        long[] nnum = new long[nums.length];
        for (int i = 0; i < nnum.length; i++) {
            nnum[i] = nums[i];
        }
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(nnum.clone(), mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(long[] num, int min) {
        for (int i = 0; i < num.length - 1; i++) {
            if (num[i] > min) {
                return false;
            }
            num[i + 1] -= min - num[i];
        }
        return num[num.length - 1] <= min;
    }
}

上面的写法虽然可以求解本题，但是不够优雅，还可以继续优化。因为要从左到右进行模拟，如果最左边的值为0，则可以增大k，而右边的元素可以减小k，在多次操作的情况下数组可能会爆int。所以要创建long型数组。

而且在模拟的过程中需要对原数组进行侵入式修改，所以每次要clone一个数组进行修改。这就导致代码不优雅。

我们可以保存一个元素tmp，用于记录左边的元素增大了多少值，如果当前元素 - tmp大于k，则return false，每次遍历要更新这个tmp。

这里还有一个关于求上界的小技巧，因为普通方法求上界比较复杂，所以上面题解中left用的是下界，这个几乎不影响时间复杂度。

下面给一个求上界的简单方法。

假设要计算 $ \left\lfloor \frac{a}{b} \right\rfloor，a > 0, b > 0 $。可以用 $ \frac{a + b - 1}{b} $代替。我们不妨可以模拟一下，不妨设a = b x k + c

当a % b == 0时，即c == 0，取上界的结果是k，而(a + b - 1) / b = (a - 1) / b + 1，又因为a - 1 = b x k - 1 = b x (k - 1) + (b - 1)，在计算机中，(a - 1) / b = k - 1，所以(a - 1) / b + 1 = k，两者相等。
当 a % b != 0时，即c >= 1，取上界的结果是k + 1，而(a + b - 1) / b = (a - 1) / b + 1，又因为a - 1 = b x k + c - 1 = b x k + (c - 1)，且c - 1 >= 0，所以(a - 1) / b = k，所以(a - 1) / b + 1 = k + 1，两者也相等。

所以以后计算上界就可以直接使用该公式。

class Solution {
    public int minimizeArrayValue(int[] nums) {
        int n = nums.length;
        int left = (Arrays.stream(nums).sum() + n - 1) / n;
        int right = Arrays.stream(nums).max().getAsInt();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(mid, nums)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int limit, int[] nums) {
        long tmp = 0;
        for (int x : nums) {
            if (x - tmp > limit) {
                return false;
            }
            tmp += limit - x;
        }
        return true;
    }
}

动态规划

本题还有更巧妙的算法，我们想如果索引0到m区间的最大值最小为k，那么如果nums[m + 1]小于等于k，肯定不会对原数据产生影响，因为该值不可能向左平均，越平均会使最大值越大。

所以当nums[m + 1]的值大于k时，需要将nums[m + 1]的值向左边平均。

平均后元素最大值的下界为均值的上取整，不妨记为x，如果x <= k，则不会影响原来的最大值，因为题意的操作只会让左边的元素变大，例如[11, 1]，当遍历到1时，不会让11变小，所以1不会改变结果。如果x > k，则可以将x平均给其他的其他的元素，使得区间[0, m + 1]的最大值最小为x。

用dp[i]表示区间[0, i]的最大值最小，则可以递归推出dp[n - 1]。

所以算法的时间复杂度为O(n)，空间复杂度为O(1)。，因为dp每次只用到前一个状态的值，因此可以使用滚动数组优化到O(1)。实现非常简单，为了更加清晰的表达，代码中不展示，小伙伴们自己尝试。

class Solution {
    public int minimizeArrayValue(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        long sum = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum += nums[i];
            dp[i] = dp[i - 1];
            if (nums[i] > dp[i - 1]) {
                dp[i] = Math.max(dp[i - 1], (int) ((sum + i) / (i + 1)));
            }
        }
        return dp[n - 1];
    }
}

刷题总结

本题动态规划的做法比较难以想到，我对小伙伴们的要求是能够10分钟内写出二分查找的算法，这是本题最重要的解法。