欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

410. 分割数组的最大值

程序员文章站 2022-07-01 17:16:45
...

410. 分割数组的最大值

410. 分割数组的最大值

解题思路

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

方法1:二分法

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

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

所以,m 的取值范围为 1 <= m <= n,因此,最大值的最小值的范围为[10,32][10, 32]

我们利用二分法查找,找出符合 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;
    }
}

410. 分割数组的最大值

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