难度: Hard
给定一个非负整数数组 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
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
max_val = max(nums)
array_sum = sum(nums)
left = max_val
right = array_sum
while right > left:
mid = (right-left) // 2 + left
if self.canSplit(nums, k, mid):
right = mid
else:
left = mid + 1
return left
def canSplit(self, nums, k, max_val):
count = 1
array_sum = 0
for num in nums:
array_sum += num
if array_sum > max_val:
count += 1
array_sum = num
if count > k:
return False
return True
此题解采用二分查找的方法。首先定义二分查找的左边界为数组中的最大值，右边界为数组所有元素之和。二分查找的目标是找到最小的最大子数组和，使得数组可以被分割成k个子数组。在二分查找的每一步中，判断当前的中间值是否可以将数组分割成k个子数组，如果可以，则右边界更新为中间值；如果不可以，则左边界更新为中间值加一。最终二分查找的结果即为答案。判断是否可以分割成k个子数组的方法是，遍历数组，累加数组元素，如果当前子数组和超过了最大允许值，则开始一个新的子数组，同时子数组的数量加一。如果最终子数组的数量大于k，则说明无法分割，返回False；否则返回True。
时间复杂度: O(n*log(sum-max))，其中sum为数组元素之和，max为数组中的最大值；极端情况下退化为O(n)
空间复杂度: O(1)
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
max_val = max(nums) # 数组最大值作为二分查找左边界
array_sum = sum(nums) # 数组和作为二分查找右边界
left = max_val
right = array_sum
while right > left:
mid = (right-left) // 2 + left # 计算中间值
if self.canSplit(nums, k, mid): # 判断中间值是否可以分割
right = mid # 可以分割，更新右边界
else:
left = mid + 1 # 不可以分割，更新左边界
return left # 二分查找的最终结果
def canSplit(self, nums, k, max_val):
count = 1 # 当前子数组计数
array_sum = 0 # 当前子数组和
for num in nums:
array_sum += num # 累加当前元素到子数组
if array_sum > max_val: # 子数组和超过最大允许值
count += 1 # 新开一个子数组
array_sum = num # 重置子数组和为当前元素
if count > k: # 子数组数量超过k
return False # 无法分割
return True # 可以分割
在二分查找中选择数组中的最大值作为左边界是因为无论如何分割数组，任何一个子数组中至少会包含一个元素，因此该子数组的和至少为数组中的最大值。这保证了左边界是一个合理和有效的起点，确保所有分割后的子数组的最大和不会小于这个值。
二分查找的停止条件设置为当右边界大于左边界时，是因为我们需要在左右边界相遇或交错时结束搜索，这表示找到了满足条件的最小可能值。当左右边界相等时，确实可能出现，此时这个值就是可能的最小最大子数组和。如果继续进行二分查找，将不会有新的中点产生，会导致重复计算或无限循环。
在函数canSplit中，如果当前元素num大于max_val，这种情况下，我们无法将num加入到当前子数组中而不超过max_val的限制。此时必须将num作为新的子数组的开始，即使它单独一个元素就超过了max_val。这种处理确保了算法的正确性，但实际上在调用canSplit之前，我们已经设定了左边界为数组中的最大值，理论上这种情况不应出现，除非在初始条件设置错误。
在实际应用中，确定二分查找中的mid是否可以有效地将数组分割成k个子数组，是通过实现一个辅助函数canSplit来完成的。这个函数通过尝试使用mid作为最大子数组和来分割数组，如果在限定的最大值内可以将数组分割成不超过k个子数组，则返回True，表示mid是一个有效的值；否则返回False。通过这种方式，二分查找逐步调整mid值，直到找到最小的符合条件的mid。