求解思路
这道题与其直接想"怎么分割数组"，不如先问"如果我规定每个子数组的和不能超过某个值 x，那最少需要分成几部分？"
通过这个反向思考，我们可以用二分搜索来找答案。
想象一下调节音量的过程，我们在 0 到数组总和之间不断试探一个"限制值"，每次尝试时都检查：
在这个限制下能否把数组分成不超过 k 个部分。
如果可以做到，说明这个限制还能再小一点，我们就往更小的方向试；
如果做不到，说明限制太严格了,我们就往更大的方向试。
这样一步步逼近,最终就能找到那个"恰好能分成 k 个部分"的最小限制值，这个值就是答案。
代码实现
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
|
public static int splitArray(int[] nums, int k) {
// 计算数组总和，这是二分搜索的右边界
long sum = 0;
for (int num : nums) {
sum += num;
}
long ans = 0;
// 在 [0, sum] 区间进行二分搜索
for (long l = 0, r = sum, m, need; l <= r;) {
// 计算中点
m = l + ((r - l) >> 1);
// 关键：如果限制每部分和不超过 m，需要分成几个部分?
need = f(nums, m);
if (need <= k) {
// 如果分成的部分数 <= k，说明 m 可行
// 但可能还能更小，继续在左半边找
ans = m;
r = m - 1;
} else {
// 如果需要分成的部分 > k，说明 m 太小了
// 需要增大限制，在右半边找
l = m + 1;
}
}
return (int) ans;
}
// 辅助函数：给定限制 limit，计算最少需要分成几个部分
public static int f(int[] arr, long limit) {
int parts = 1; // 至少需要 1 个部分
int sum = 0; // 当前部分的累加和
for (int num : arr) {
// 如果单个元素就超过限制，无法分割
if (num > limit) {
return Integer.MAX_VALUE;
}
// 如果加上当前元素会超过限制
if (sum + num > limit) {
parts++; // 开启新的部分
sum = num; // 当前元素作为新部分的起始
} else {
sum += num; // 继续累加到当前部分
}
}
return parts;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~