0410. 分割数组的最大值 #

标签：贪心、数组、二分查找、动态规划、前缀和
难度：困难

题目大意 #

给定一个非负整数数组 nums 和一个整数 m，将数组分成 m 个非空的连续子数组，要求使 m 个子数组各自和的最大值最小，并求出子数组各自和的最大值。

解题思路 #

先来理解清楚题意。题目的目的是使得 m 个连续子数组各自和的最大值最小。意思是将数组按顺序分成 m 个子数组，然后计算每个子数组的和，然后找出 m 个和中的最大值，要求使这个最大值尽可能小。最后输出这个尽可能小的和最大值。

可以用二分查找来找这个子数组和的最大值，我们用 ans 来表示这个值。ans 最小为数组 nums 所有元素的最大值，最大为数组 nums 所有元素的和。即 ans 范围是 [max(nums), sum(nums)]。

所以就确定了二分查找的两个指针位置。left 指向 max(nums)，right 指向 sum(nums)。然后取中间值 mid，计算当子数组和的最大值为 mid 时，所需要分割的子数组最少个数。

如果需要分割的子数组最少个数大于 m 个，则说明子数组和的最大值取小了，不满足条件，应该继续调大，将 left 右移，从右区间继续查找。
如果需要分割的子数组最少个数小于或等于 m 个，则说明子数组和的最大值满足条件，并且还可以继续调小，将 right 左移，从左区间继续查找，看是否有更小的数组和满足条件。
最终，返回符合条件的最小值即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def get_count(x):
            total = 0
            count = 1
            for num in nums:
                if total + num > x:
                    count += 1
                    total = num
                else:
                    total += num
            return count

        left = max(nums)
        right = sum(nums)
        while left < right:
            mid = left + (right - left) // 2
            if get_count(mid) > m:
                left = mid + 1
            else:
                right = mid
        return left