leetcode 410.分割数组的最大值

原题

410.分割数组的最大值

题解

方法一 试值+二分

1、 我们既然要求出的是每组数字之和的最大值，并且尽可能让这个最大值最小，这样的话暴力组合出所有情况不现实。那么我们就可以反着来思考，那就是，假设一个最小的“和的最大值”，假如设为max，再带入到数组中看是否能够保证每组和的值都不大于max的情况下，分出的组数不大于m。
2、 假设max的临时值是max1，我们可以不断遍历数组，同时，从第一个数字开始累加，累加值到sum，每当累加到最大的不大于max1的值的时候（事实是当累加到大于m的时候，把数组指针往前播一个位置），就要开始把sum归零并且继续地向后挨个儿累加。直到最后：情况一是取出来的组数不到m或者刚好等于m，就已经取完了，这种情况说明真正的max值是不大于max1的也就是徐要往小了取才能接近正确答案；情况二是还没取完就已经取到了m组，那么此时就说明max1小了，需要往大了取才能接近正确答案。
3、 那么这个max如何寻找呢？遍历从1到最大int的方法显然不现实，我们采用的是二分法。具体操作为设置左边界zuo的初始值为0，右边界初始值设置为最大的int；不断地去mid为zuo和you的中间值（也就是现在的mid即为步骤2里面的max1），进行步骤2中的判断，情况一的时候you的值移动到mid处，情况二的时候mid值移动到mid+1处；如此反复，直到zuo和you相同，那么此时的zuo就是所求得的步骤2里面正确的max。
本思路java代码示例：

/*
@v7fgg
执行用时：2 ms, 在所有 Java 提交中击败了40.41%的用户
内存消耗：37 MB, 在所有 Java 提交中击败了33.33%的用户
2020年7月16日 12:20
*/
class Solution {
    public int splitArray(int[] nums, int m) {
        int zuo=0;
        int you=Integer.MAX_VALUE;
        while(zuo<you){
            int mid=zuo+(you-zuo)/2;
            int tianshu=0;
            long sum=0;//小心测试例：[1,2147483647] 2
            boolean bukeyi=false;
            for(int i=0;i<nums.length;i++){
                if(tianshu==m){
                    zuo=mid+1;
                    bukeyi=true;
                    break;
                }
                sum+=nums[i];
                if(sum>mid){
                    i--;
                    sum=0;
                    tianshu++;
                }
            }
            if(bukeyi){continue;}
            you=mid;
        }
        return zuo;
    }
}