leetcode-split-array-largest-sum

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/split-array-largest-sum/

　　给你非负整数数组和整数m，让你把数组分成连续的m段子数组，求所有分法的m字段和的最大值的最小化

题目分析

　　最小化最大值问题，可以考虑二分查找，二分check的条件是所有m子段和都小于等于某个数字d，而check方法的实现利用贪心的思想，从前向后扫描原数组，每次凑连续几个数，是这几个数的和尽可能接近d，但不能大于d，这样就得到一组，然后继续向后扫描，一直到数组结尾，看看最后能得到几组，这个组数如果小于等于m，那么d是可行的，check返回true。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    private boolean check(int d, int[] nums, int m) {
        int len = nums.length;
        int sum = 0;
        int count = 0;
        for(int i = 0; i < len; i++) {
            if(nums[i] > d) {
                return false;
            }
            if(sum + nums[i] > d) {
                sum = nums[i];
                count++;
                if(count >= m) {
                    return false;
                }
            } else {
                sum += nums[i];
            }
        }
        return true;
    }
    
    public int splitArray(int[] nums, int m) {
        int len = nums.length;
        int left = 0;
        int right = 0x7fffffff;
        int mid;
        while(right - left > 1) { //(left, right]
            mid = (left + right) / 2;
            if(check(mid, nums, m)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}