[LeetCode]410. 分割数组的最大值(Split Array Largest Sum)

题目描述

给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

示例:

输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8],
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。

解题思路

二分法。目标值一定是在数组的最大值和数组和之间的,对这个区间进行二分。
二分思路:对当前的最大和,模拟子数组的生成过程,每个子数组都选到最接近最大和,最后看分到的子数组的数量来决定使用哪一边的区间。若子数组数量大于 m,则说明最大和取得太小了,反之。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
max_num = max(nums)
if len(nums) == m:
return max_num
l, r = max_num, sum(nums)
while l < r:
mid = (l + r) // 2

# 模拟子数组的分割
tmp_sum, count = 0, 1
for num in nums:
tmp_sum += num
if tmp_sum > mid:
tmp_sum = num
count += 1

if count > m:
# 若子数组的数量大于 m,说明最大和太小了,分割使用右边
l = mid + 1
else:
r = mid
return l

执行用时:56 ms
内存消耗:14 MB