MENU

LeetCode410. 分割数组的最大值

July 9, 2018 • Read: 273 • LeetCode

image
这道题看着好像没什么思路,但其实可以利用二分法来做,二分法中的mid就是最终要返回的值,也就代表着子数组的和最小的值

我们首先还是设置左右区间,左区间L=0,右区间是数组所有元素的和再加1,因为二分法的区间一般是左闭右开

然后就是将数组进行打包,从第一个开始打包,如果第一个加上后一个还不大于mid,那就将其继续加上后一个,直到大于mid了,那就说明这个包已经放不下了,后面的至少还需要再开一个包,每开一个包,m的数量就减少一个,最后return m究竟是否大于0

如果返回的是true,那我们再试试mid更小的时候是否也成立,将R = mid,把mid的值赋给R;如果返回的是false,说明mid太小了,那我们应该把mid稍微放大一点,看看还行不行,将L = mid + 1,把mid+1的值赋给L。最终mid的值就是所求的值。建议带入样例自己模拟一遍这个过程

class Solution {
    public boolean guess(long mid,int[] nums,long m) {
        long sum = 0;
        for(int i = 0;i < nums.length;i++) {
            if(sum + nums[i] > mid) {
                --m;
                sum = nums[i];
                if(sum > mid)
                    return false;
            }
            else
                sum += nums[i];
        }
        return m > 0;
    }
    public int splitArray(int[] nums, int m) {
        long ans = 0;
        long L = 0,R = 1;
        for(int i = 0;i < nums.length;i++) 
            R += nums[i];
        while(L < R) {
            long mid = (L + R) / 2;
            if(guess(mid,nums,m)) {
                ans = mid;
                R = mid;
            }
            else
                L = mid + 1;
        }
        return (int)ans;
    }
}
最后编辑于: October 10, 2018
Archives Tip
QR Code for this page
Tipping QR Code