分割数组的最大值Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

示例 1：

输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：

输入：nums = [1,2,3,4,5], m = 2
输出：9

示例 3：

输入：nums = [1,4,4], m = 3
输出：4

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 10⁶
1 <= m <= min(50, nums.length)

# 思路

    /*
    二分法
    nums = [7,2,5,10,8]
    m = 1，那么整个数组作为一部分，最小的最大值为 32
    m = n，那么每个元素作为一个子数组，从所有元素选取最大值，最小的最大值小为 10

    m 的取值范围为 1 <= m <= n，因此，最大值的最小值的范围为 [10, 32]

    我们利用二分法查找，找出符合 m 的最大值的最小的结果
    二分过程：
    left = 10;
    right = 32
    mid = (left + right) >>> 1 = 21（这个 21 就是一个子数组的最大容量）
    我们假设刚开辟的用来存储的子数组个数 cnt = 1
    那么根据贪心思想，我们将数组元素按顺序逐个往里放
    因此就有如下过程：
    7 < 21
    7 + 2 < 21
    7 + 2 + 5 < 21
    7 + 2 + 5 + 10 > 21
     至此，我们可以看出一个 21 容量的子数组是无法容纳整个数组元素的，因此我们需要开辟第二个子数组来存储剩下的数组元素
    cnt = cnt + 1 = 2
    10 < 21
    10 + 8 < 21
    我们发现，两个子数组可以将整个数组元素放入，而 cnt 刚好等于 m，因此 [7,2,5] 和 [10,8] 就是分割出来的两个子数组，最小的最大值为 18

    为什么是放入元素直到放不下为止？因为要求的是连续子数组，我们需要保证每个连续的子数组的元素和都尽可能的接近 21

    如果我们最终得到的 cnt > m，那么表示我们划分出太多的子数组，也就是意味着一个子数组的容量太少，我们需要再扩大容量，即 left = mid + 1，然后继续进行二分
    如果我们最终得到的 cnt < m，那么表示我们划分出太少的子数组，也就是意味着一个子数组的容量太大，需要减少容量，即 right = mid - 1
    */

# 解法



class Solution {
        /*
        二分法
        nums = [7,2,5,10,8]
        m = 1，那么整个数组作为一部分，最小的最大值为 32
        m = n，那么每个元素作为一个子数组，从所有元素选取最大值，最小的最大值小为 10

        m 的取值范围为 1 <= m <= n，因此，最大值的最小值的范围为 [10, 32]

        我们利用二分法查找，找出符合 m 的最大值的最小的结果
        二分过程：
        left = 10;
        right = 32
        mid = (left + right) >>> 1 = 21（这个 21 就是一个子数组的最大容量）
        我们假设刚开辟的用来存储的子数组个数 cnt = 1
        那么根据贪心思想，我们将数组元素按顺序逐个往里放
        因此就有如下过程：
        7 < 21
        7 + 2 < 21
        7 + 2 + 5 < 21
        7 + 2 + 5 + 10 > 21
         至此，我们可以看出一个 21 容量的子数组是无法容纳整个数组元素的，因此我们需要开辟第二个子数组来存储剩下的数组元素
        cnt = cnt + 1 = 2
        10 < 21
        10 + 8 < 21
        我们发现，两个子数组可以将整个数组元素放入，而 cnt 刚好等于 m，因此 [7,2,5] 和 [10,8] 就是分割出来的两个子数组，最小的最大值为 18

        为什么是放入元素直到放不下为止？因为要求的是连续子数组，我们需要保证每个连续的子数组的元素和都尽可能的接近 21

        如果我们最终得到的 cnt > m，那么表示我们划分出太多的子数组，也就是意味着一个子数组的容量太少，我们需要再扩大容量，即 left = mid + 1，然后继续进行二分
        如果我们最终得到的 cnt < m，那么表示我们划分出太少的子数组，也就是意味着一个子数组的容量太大，需要减少容量，即 right = mid - 1
        */
    public int splitArray(int[] nums, int m) {

        int left = 0;
        int right = 0;
        for(int num : nums){
            left = Math.max(left, num);
            right += num;
        }
         //二分 logn，内部遍历数组 n，时间复杂度 O(nlogn)
        while(left < right){
            int cnt = 1;
            int mid = (left + right) >>> 1;
            int sum = 0;
            for(int num : nums){
                if(sum + num > mid){
                    sum = 0;
                    cnt++;
                }
                sum += num;
            }
            if(cnt > m){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# 总结

分析出几种情况，然后分别对各个情况实现