410. 分割数组的最大值

image

解题思路

审题之后可以得出结论，结果必定在[max(nums), sum(bums)] 这个区间内，因为左端点对应每个单独的元素构成一个子数组，右端点对应所有元素构成一个子数组。

方法1：二分法

通过示例 nums = [7,2,5,10,8] 来进行分析

当 m = 1, 那么整个数组作为一部分，最小的最大值为32
当 m = n, 那么每个元素作为一个子数组，从所有元素选取最大值，最小的最大值为 10

所以，m 的取值范围为 1 <= m <= n，因此，最大值的最小值的范围为

我们利用二分法查找，找出符合 m 的最大值的最小的结果。

二分过程：

lower = 10;
upper = 32;
mid = (left + right) >>> 1 = 21 (这个 21 就是一个子数组的最大容量)

我们假设刚开辟的用来存储的子数组个数 count = 1
那么根据贪心思想，我们将数组元素按顺序逐个往里放
因此就有如下过程： \

7 < 21
7 + 2 < 21
7 + 2 + 5 < 21
7 + 2 + 5 + 10 > 21

至此，我们可以看出 21 容量的子数组是无法容纳整个数组元素的，因此我们需要开辟第二个子数组来存储剩下的数组元素。
count = count + 1 = 2

10 < 21
10 + 8 <21

我们发现，两个子数组可以将整个数组元素放入，而 count 刚好等于 m，因此 [7,2,5] 和 [10, 8] 就是分割出来的两个子数组，最小的最大值为 18。

为什么是当如元素直到放不下为止？因为要求的是连续子数组，我们需要保证每个连续的子数组的元素都尽可能的接近 21。

如果我们最终得到的 count > m, 那么表示我们划分出太多的子数组，也就是意味着一个子数组的容量太小，我们需要再扩大容量，即 lower = mid + 1, 然后继续进行二分查找
如果我们最终得到的 count < m, 那么表示我们划分出太少的子数组，也就是意味着一个子数组的容量太大，需要减少容量，即 upper = mid

class Solution {
    public int splitArray(int[] nums, int m) {
        // lower: max(nums[i])
        // upper: sum(nums)
        // lower <= k < upper
        long lower = 0, upper = 0, k = 0;
        for (int i = 0; i < nums.length; i++) {
            lower = Math.max(lower, nums[i]);
            upper += nums[i];
        }
        // 进行二分查找
        long mid = 0;
        while (lower < upper) {
            mid = lower + ((upper - lower ) >> 1);
            if(canSplit(nums, m, mid)) {
                upper = mid;
            } else {
                lower = mid + 1;
            }
        }
        if (canSplit(nums, m, lower)) {
            return (int)lower;
        }
        return (int)upper;
    }
    // 检测数组是否能够分成m个非空的连续子数组，并且使得子数组之和的最大值不超过k
    private boolean canSplit(int[] nums, int m, long k) {
        // 当前子数组的sum
        long sum = 0;
        // 当前切分的数量
        long count = 0;
        for (int i = 0; i < nums.length; i++) {
            // 当前子数组和+ nums[i] 大于 k，说明在这需要切分一次，并清空子数组和sum
            if (sum + nums[i] > k) {
                count++;
                sum = 0;
            }
            //  对连续子数组进行相加
            sum += nums[i];
        }
        // 如果最后，切分的次数是小于m，那就说明存在k这样的一个分法的
        // 因为，如果说极限条件是小于m的话，那我想分成m个，
        // 那我只可能切比count更多的次数，意味着子数组和的最大值就更小
        return count < m;
    }
}

部分图片来源于网络，版权归原作者，侵删。