想要精通算法和SQL的成长之路 - 分割数组的最大值

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 分割数组的最大值

原题链接

首先面对这个题目，我们可以捕获几个关键词：

• 非负整数。
• 非空连续子数组。

那么我们假设分割后的子数组，和的最大值是M，对应分割的子数组个数为N。他们之间必然存在以下关系：

• 分割的子数组个数 N 越多，对应的和最大值 M 也就越小。
• 分割的子数组个数 N 越少，对应的和最大值 M 也就越大。

那么我们以每组和的最大值作为切入点，案例如下：

• 设置 数组各自和的最大值 为 20，此时分割依然是 [7, 2, 5, | 10, 8]，此时分割的数组数为2。
• 设置 数组各自和的最大值 为 19，此时分割依然是 [7, 2, 5, | 10, 8]，此时分割的数组数为2。
• 设置 数组各自和的最大值 为 18，此时分割依然是 [7, 2, 5, | 10, 8]，此时分割的数组数为2。
• 设置 数组各自和的最大值 为 17，此时分割就变成了 [7, 2, 5, | 10, | 8]，此时分割的数组数为3。

而我们题目要求分割组数是2，那么满足这个条件的几种情况，我们再取最大和最小的情况，最终得到结果是18。

1.1 二分法

二分的目标对象是什么？我们可以二分：数组各自和的最大值。那么二分法，就应该有初始区间：

• left：可以是当前数组的最大元素值。（单个元素一组）
• right：可以是当前数组的总和。（所有元素成一组）

那么我们二分后取得 mid：

int mid = left + (right - left) / 2;

接下来我们就要对数组进行分组计算了，对数组从左往右按顺序分组，使得分组后的各个子数组和不能超过mid。我们可以编写个helper函数：

public int helper(int[] nums, int maxGroupSum) {// 分组数最小是1int res = 1;int curSum = 0;for (int num : nums) {// 如果加入当前元素会导致和超过限制，那么就另外再分一组if (curSum + num > maxGroupSum) {res++;curSum = 0;}curSum += num;}return res;
}

我们计算好分组后的个数groupNum之后，就需要和题目传入的k进行对比：

• groupNum > k ： 说明数组各自和的最大值还是小了，我们应该调大数组各自和的最大值。即left = mid +1。
• 反之：right = mid;

最终代码如下：

public int splitArray(int[] nums, int k) {int max = 0, sum = 0;for (int num : nums) {max = Math.max(max, num);sum += num;}int left = max, right = sum;while (left < right) {int mid = left + (right - left) / 2;// 如果分组数比 k 还要大，说明每个分组的和最大值还是小了int groupNum = helper(nums, mid);if (groupNum > k) {left = mid + 1;} else {right = mid;}}return left;
}public int helper(int[] nums, int maxGroupSum) {// 分组数最小是1int res = 1;int curSum = 0;for (int num : nums) {// 如果加入当前元素会导致和超过限制，那么就另外再分一组if (curSum + num > maxGroupSum) {res++;curSum = 0;}curSum += num;}return res;
}