原题
给定一个非负整数数组和一个整数 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，在所有情况中最小。
解法
思想
二分查找。要分成连续子数组，子数组的和的下限和上限分别是值最大的元素和所有元素之和，根据和不大于mid的子数组个数来逼近一个值，就是分割数组的最大值。
代码
class Solution {
public int splitArray(int[] nums, int m) {
int max = nums[0];
int sum = 0;
for(int i:nums){
if(i>max) max = i;
sum += i;
}
long start = max, end = sum;
while(start<end){
long mid = (start + end)/2;
long temp = 0;
int count = 1;
for(int i:nums)
{
temp += i;
if(temp>mid)
{
temp = i;
++count;
}
}
if(count>m)
start = mid + 1;
else
end = mid;
}
return (int)start;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode410-%e5%88%86%e5%89%b2%e6%95%b0%e7%bb%84%e7%9a%84%e6%9c%80%e5%a4%a7%e5%80%bc/
相关推荐
-
leetcode160-相交链表
原题 编写一个程序，找到两个单链表相交的起始节点。 如下面的两个链表： 在节点 c1 开始相交。 示例 1： 输入： intersectVal = 8, listA = [4,1,...
-
力扣杯春季个人赛-剧情触发时间
这次的个人赛真是让我认清了自己的实力。。两道困难题都没做出?，虽然大家的通过率也不咋地。。 最后排名 我记录一道做出来的题吧，这道题是一道中等题，通过率如下，虽然题目不难，但由于时...
-
leetcode752-打开转盘锁
原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由...
-
程序员面试金典01.06-字符串压缩
原题（来源Leetcode） 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字...
-
leetcode118-杨辉三角
原题 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]...
-
leetcode341-扁平化嵌套列表迭代器
原题 给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数，或者是另一个列表。 示例1： 输入: [[1,1],2,[1,1]]...
-
leetcode394-字符串解码
原题 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意...
-
leetcode744-寻找比目标字母大的最小字母
原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子，如果目标字母tar...
-
leetcode705-设计哈希集合
原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说，你的设计应该包含以下的功能 add(value)：向哈希集合中插入一个值。 contains(value) ：返回哈希集合...
