410. 分割数组的最大值

题目链接：410. 分割数组的最大值

题目描述

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。

设计一个算法使得这 k 个子数组各自和的最大值最小。

核心思考：对答案的值域进行二分查找

这道题的逻辑底色与 1011. 在 D 天内送达包裹的能力 完全一致。

题目要求寻找“子数组各自和的最大值的最小值”。我们可以通过二分查找直接在可能的结果范围内，寻找这个最小的“最大子数组和”。

1. 确定二分查找边界

• 左边界（最小值）：如果数组被分割成与元素个数相同的子数组（也就是每个元素单独成一组），此时“子数组和的最大值”就是整个数组中的最大元素。因此，左边界为 left = max(nums)。
• 右边界（最大值）：如果不分割数组（也就是 k = 1），此时“子数组和的最大值”就是数组所有元素的总和。因此，右边界为 right = sum(nums)。

2. 验证分割数量

我们用一个函数 nums_of_array 来验证：在限制子数组最大和为 x 的情况下，数组最少会被分割成几段。
具体做法是顺序遍历数组并累加元素。如果当前子数组的元素和超出了设定的最大值 x，说明当前元素必须放入一个新的子数组中，因此所需子数组的数量 pool 增加 1，并将当前元素作为新子数组的起始值。

3. 根据分割数量调整值域

利用二分查找测试中间值 mid 作为最大和：

• 如果按 mid 分割得到的子数组数量 temp 小于等于 k：说明设定的最大和不仅合法，甚至可能有点偏大（分出的数组比较少）。我们可以尝试寻找更小的最大和，因此向左收缩右边界（right = mid - 1）。
• 如果分割出的子数组数量 temp 大于 k：说明设定的最大和太小了，导致数组被切得太碎、段数过多。必须增大这个限制，因此向右移动左边界（left = mid + 1）。

当循环条件终止时，最终得到的 left 就是刚好满足分割成 k 组的最小的最大子数组和。

解题思路 (Python)

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        # 在这个最大值下分割，会分割成几个数组？
        def nums_of_arry(nums,x): 
            count = 0
            pool = 1
            for i in nums:
                if count + i <= x:
                    count += i
                else:
                    count = i
                    pool += 1
            return pool
        
        left = max(nums)
        right = sum(nums)

        while left <= right:
            mid = left + (right - left) // 2
            temp = nums_of_arry(nums,mid)
            # 用这个分出来的数组多了，说明容量太小，应该继续提升。 left = mid + 1
            # 用这个分出来的数组少了，说明容量太大了，最大值应该继续降低 right = mid -1
            # 选择靠左侧的 right = mid - 1
            if temp <= k:
                right = mid - 1
            else:
                left = mid + 1
        return left

复杂度分析

• 时间复杂度：$O(N \log(\Sigma nums))$，其中 $N$ 是数组 nums 的长度，$\Sigma nums$ 是数组中所有元素的总和。二分查找的范围是数据的总和，因此需要进行约 $O(\log(\Sigma nums))$ 次二分。每次二分测试都需要遍历一次原数组，时间消耗为 $O(N)$。两者呈相乘关系。
• 空间复杂度：$O(1)$。算法只使用了几个常数级别的变量辅助记录状态，没有使用与数据规模相关的额外空间。