给定一个非负整数数组?
nums
?和一个整数?k
?,你需要将这个数组分成?k
?个非空的连续子数组。设计一个算法使得这?
k
?个子数组各自和的最大值最小。
?
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
}
};
看到”最大的最小“自然想到二分
那么关键就在于给定x,如何判断原数组是否能够划分为最大值不超过x的k个子数组
我们贪心地思考,如果原数组能够划分为最大值不超过x的j个子数组,j < k,那么一定也可以通过拆解某些子数组从而得到k个子数组
所以我们的check函数,遍历数组,贪心累加,如果sum > x,我们就cnt + 1,然后sum = x
最终取决于cnt <= k
很经典的二分+贪心的题目
时间复杂度:O(n) 空间复杂度:O(1)
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int r = 0 , l = 0;
for(auto x : nums) r += x , l = max(l , x);
function<bool(int)> check = [&](int t)
{
int cnt = 1 , s = 0;
for(auto x : nums){
if(s + x > t)
s = x , cnt++;
else
s += x;
}
return cnt <= k;
};
while(l < r)
{
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
return r;
}
};