算法
(二分答案) $O(nlog(n))$
左端为max
,右端为sum
(数组和),二分答案check
即可。
C++ 代码
class Solution {
public:
bool check(int max_val, vector<int>& nums, int m) {
int cnt = 1;
long long sum = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > max_val) {
return false;
}
if (sum + nums[i] > max_val) { //如果当前连续和大于max_val
cnt++; //计数+1
sum = nums[i]; //sum更新为num[i]
} else {
sum += nums[i];
}
}
return cnt <= m;
}
int splitArray(vector<int>& nums, int m) {
long long l = 0, r = 0;
for (int i = 0; i < nums.size(); ++i) {
l = max((int)l, nums[i]); //确定二分查找的左右端点
r += nums[i];
}
int ans = 0;
while(l <= r) {
long long mid = (l + r) / 2;
if (check(mid, nums, m)) { //二分check
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
};