力扣题目链接:https://leetcode.cn/problems/split-array-largest-sum/
给定一个非负整数数组 nums
和一个整数?m
,你需要将这个数组分成?m
?个非空的连续子数组。
设计一个算法使得这?m
?个子数组各自和的最大值最小。
?
示例 1:
输入:nums = [7,2,5,10,8], m = 2 输出:18 解释: 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
示例 2:
输入:nums = [1,2,3,4,5], m = 2 输出:9
示例 3:
输入:nums = [1,4,4], m = 3 输出:4
?
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
写一个函数check(s)
,返回能否
将数组nums
划分为k
部分且每一部分的最大值不超过s
。
实现方法很简单,使用一个变量
cnt
来记录当前部分的元素和。遍历数组,如果当前元素大于
s
,则必不可能成功划分,直接返回false
。若
cnt
加上当前元素超过了s
,则将当前元素划分为一组(k--
、cnt = 0
)。
cnt
加上当前元素。遍历结束后,判断
k - 1
是否大于等于0
。若是,则返回true
,否则返回false
。
有了这样的函数,我们只需要在主函数中写一个二分,枚举值mid
是否能通过check
。
l
初始值为0
,r
初始值为“无穷大”(数组中所有元素之和再加一)。当
l < r
时,令 m i d = ? l + r 2 ? mid = \lfloor \frac{l+r}{2} \rfloor mid=?2l+r??。如果
check(mid)
通过了,则说明mid
为一种合法分法,尝试更小的值能否成功划分(令r = mid
)否则,说明
mid
太小了,无法划分,尝试更大的值能否成功划分(令l = mid + 1
)
二分结束后,l = r
,返回l
即为答案。
class Solution {
private:
bool check(vector<int>& nums, int k, int s) {
int cnt = 0;
for (int t : nums) {
if (t > s) {
return false;
}
if (t + cnt > s) {
k--;
cnt = 0;
}
cnt += t;
}
return --k >= 0;
}
public:
int splitArray(vector<int>& nums, int k) {
int l = 0, r = accumulate(nums.begin(), nums.end(), 0) + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(nums, k, mid)) {
r = mid;
}
else {
l = mid + 1;
}
}
return l;
}
};
# from typing import List
class Solution:
def check(self, k: int, s: int) -> bool:
cnt = 0
for t in self.nums:
if t > s:
return False
if cnt + t > s:
k -= 1
cnt = 0
cnt += t
return k - 1 >= 0
def splitArray(self, nums: List[int], k: int) -> int:
self.nums = nums
l, r = 0, sum(nums) + 1
while l < r:
mid = (l + r) >> 1
if self.check(k, mid):
r = mid
else:
l = mid + 1
return l
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/135728821