分割数组的最大值
难度:
标签:
题目描述
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], k = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], k = 2 输出：9
示例 3：
输入：nums = [1,4,4], k = 3 输出：4
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)
代码结果
运行时间: 48 ms, 内存: 16.1 MB
/*
* 题目思路：
* 1. 利用Java Stream API来实现数组操作。
* 2. 依然使用二分查找来确定最大和的最小值。
* 3. 通过Java Streams的特性进行数组元素的计算。
*/
import java.util.Arrays;
public class Solution {
public int splitArray(int[] nums, int k) {
int left = Arrays.stream(nums).max().getAsInt();
int right = Arrays.stream(nums).sum();
while (left < right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canSplit(int[] nums, int k, int maxSum) {
int count = 1, currentSum = 0;
for (int num : nums) {
if (currentSum + num > maxSum) {
count++;
currentSum = num;
if (count > k) {
return false;
}
} else {
currentSum += num;
}
}
return true;
}
}解释
方法:
此题解采用二分查找的方法。首先定义二分查找的左边界为数组中的最大值，右边界为数组所有元素之和。二分查找的目标是找到最小的最大子数组和，使得数组可以被分割成k个子数组。在二分查找的每一步中，判断当前的中间值是否可以将数组分割成k个子数组，如果可以，则右边界更新为中间值；如果不可以，则左边界更新为中间值加一。最终二分查找的结果即为答案。判断是否可以分割成k个子数组的方法是，遍历数组，累加数组元素，如果当前子数组和超过了最大允许值，则开始一个新的子数组，同时子数组的数量加一。如果最终子数组的数量大于k，则说明无法分割，返回False；否则返回True。
时间复杂度:
O(n*log(sum-max))，其中sum为数组元素之和，max为数组中的最大值；极端情况下退化为O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在二分查找中选择数组中的最大值作为左边界？
▷🦆
二分查找的停止条件为什么是当右边界大于左边界时？是否有可能出现左右边界相等的情况？
▷🦆
函数canSplit中，如果当前元素num大于max_val会发生什么？这种情况下如何处理？
▷🦆
在实际运用中，如何确定二分查找中的mid是否确实可以将数组有效地分割成k个子数组？
▷