Java实现 LeetCode 410 分割数组的最大值

410. 分割数组的最大值

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:

数组长度 n 满足以下条件:

1 ≤ n ≤ 1000

1 ≤ m ≤ min(50, n)

示例:

输入:

nums = [7,2,5,10,8]

m = 2

输出:

18

解释:

一共有四种方法将nums分割为2个子数组。

其中最好的方式是将其分为[7,2,5] 和 [10,8]，

因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

class Solution {

    //使用贪心算法，转换原题目的问题。二分法假定 mid是最大值，求m的数值

    public boolean guess(long mid,int [] nums, int m){

        long sum = 0;

        for(int i = 0; i < nums.length; i++){

            //当分隔的一边的和 大于最大值mid时， m --

            if(sum + nums[i] > mid){

                m --;

                sum = nums[i];

                //当数值的某个元素本身的值已经大于mid，说明假定mid最大值是错的，直接返回false，开始下一轮循环

                if(nums[i] > mid){

                    return false;

                }

            }else{

                sum += nums[i];

            }

        }

        return m >= 1;

    }

    public int splitArray(int[] nums, int m) {

        long L = 0, R = 1; //为了使用左开右闭，所以把右边界初始化为1

        long ans = 0;

        //确定二分法的左右边界，这里我用 左开右闭 即[0, sum + 1) ,

        for(int i = 0; i < nums.length; i ++){

            R += nums[i];

        }

        //二分法的套路

        //通过分析可以知道，当m越大，所求最大值会越小，即 m 与最大值呈现的是单调递减的关系

        while(L < R){

            long mid = (L + R) / 2;

            //判断为true时，由于是单调递减，需要把右边界左移

            if(guess(mid,nums,m)){

                ans = mid;

                R = mid;

            } else{

                L = mid + 1;

            }

        }

        return (int) ans;

    }

}

巴特西

Java实现 LeetCode 410 分割数组的最大值

410. 分割数组的最大值

最新文章

热门文章