分割数组的最大值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] <= 106
- 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
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
# 总结
- 分析出几种情况，然后分别对各个情况实现
