410. 分割数组的最大值(leetcode)

https://leetcode.cn/problems/split-array-largest-sum/description/

比较难的二分,关键点在于看出二段性,段数越多最大值越小,段数越小最大值越大,二分最大值,然后就是最大值的合法性校验(判断段数<=k),用于二分的check

class Solution {

 

    public int splitArray(int[] nums, int k) {
        // 由于k越小,最大值越大,k越大,最大值越小
        // 有二段性,单调,可以使用二分,二分最大值应该是多少
        
        int max = 0;
        int sum = 0;

        // 计算子数组各自的和的最大值的上下界
        for (int num : nums) {
            max = Math.max(max, num);
            sum += num;
        }

        // 寻找splits<=k,最大和是多少,即lowerBound(target+1)-1
        int l=max,r=sum;
        while(l<=r)
        {
            int mid= l + (r - l >> 1);
            int splits = split(nums,mid); // 尝试按照最大和为mid,来划分,看能划分出多少段
            if(splits > k)  // 大于k意味着mid过小,段数过多
                l=mid+1; // [mid+1,right]合法
            else            // mid过小
                r=mid-1; 
        }
        return l;
    }


    // 返回nums按照最大和为maxSum,最多能划分出多少段
    int split(int[] nums,int maxSum)
    {
        // 最少为1段
        int res=1;
        int tempSum=0;
        for(int i=0;i<nums.length;i++)
        {
            // 划分出一段
            if(tempSum + nums[i] > maxSum)
            {
                tempSum=0;
                res++;
            }
            tempSum+=nums[i];
        }
        return res;
    }
        

}