LeetCode410. 分割数组的最大值
image
这道题看着好像没什么思路，但其实可以利用二分法来做，二分法中的mid就是最终要返回的值，也就代表着子数组的和最小的值 我们首先还是设置左右区间，左区间L=0，右区间是数组所有元素的和再加1，因为二分法的区间一般是左闭右开 然后就是将数组进行打包，从第一个开始打包，如果第一个加上后一个还不大于mid，那就将其继续加上后一个，直到大于mid了，那就说明这个包已经放不下了，后面的至少还需要再开一个包，每开一个包，m的数量就减少一个，最后return m究竟是否大于0 如果返回的是true，那我们再试试mid更小的时候是否也成立，将R = mid，把mid的值赋给R；如果返回的是false，说明mid太小了，那我们应该把mid稍微放大一点，看看还行不行，将L = mid + 1，把mid+1的值赋给L。最终mid的值就是所求的值。建议带入样例自己模拟一遍这个过程
class Solution {
public boolean guess(long mid,int[] nums,long m) {
long sum = 0;
for(int i = 0;i < nums.length;i++) {
if(sum + nums[i] > mid) {
--m;
sum = nums[i];
if(sum > mid)
return false;
}
else
sum += nums[i];
}
return m > 0;
}
public int splitArray(int[] nums, int m) {
long ans = 0;
long L = 0,R = 1;
for(int i = 0;i < nums.length;i++)
R += nums[i];
while(L < R) {
long mid = (L + R) / 2;
if(guess(mid,nums,m)) {
ans = mid;
R = mid;
}
else
L = mid + 1;
}
return (int)ans;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读