[leetcode]410-分割数组的最大值

有空一起学习 2020年2月11日11:44:48 发表评论

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/split-array-largest-sum

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

给定一个非负整数数组和一个整数 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,在所有情况中最小。

二、题目解析

咋一看题目,完全不知道如何下手。唯一能想到的一个办法是动态规划,但是动态规划要怎么规划。。。算了,看题解吧。

看了题解才知道要用贪心+二分,所谓贪心,就是一种策略思想,在满足条件的情况下寻找最优解。找最优解的办法就是二分,而实际上也就是不断通过二分遍历和去试。

假设数组为nums,要分成m个子数组。那么不难看出和肯定是在[max(nums), sum(nums)]的范围的:

  • 当m等于数组的长度n时,每个元素一个子数组,最大和是数组中的最大元素max(nums)
  • 当m等于1时,整个数组就是一个子数组,最大和是所有数组的和sum(nums)

在了解了这个特性后,就可以使用二分不断遍历范围内的和,然后判断和是不是满足数组条件的和。

判断和是否满足条件的办法:当前遍历到的和是sum,从数组开头开始遍历,计算累加和小于等于sum的子数组总量。如果子数组的数量大于m,说明子数组太多了,也就是sum太小了,把遍历和的左边界设置为sum+1。如果子数组的数量小于或者等于m,说明子数组太少了,sum设置的太大,修改右边界为sum-1。

以测试数据为例,[7,2,5,10,8]的和范围在[10, 32]之间,获取最小的最大和的办法:

第一步,取中值mid=21,计算出来符合条件的子数组为:

子数组m的个数刚好等于2,设置right=mid-1=20,再计算mid=15,符合条件的数组:

子数组个数为3,大于要求的2,设置left=mid+1=16,计算mid=(16+20)/2=18,符合条件的数组:

子数组个数为2,满足题目要求,设置right=mid-1=17,计算mid=(16+17)/2=16,符合条件的数组:

子数组个数为3,大于要求的2,设置left=mid+1=17,计算mid=(17+17)/2=17,符合条件的数组:

子数组个数还是3,大于要求的2,设置left=mid+1=18,此时left大于right(17),遍历结束,返回18。

三、示例代码

3.1 代码

[leetcode]410-分割数组的最大值

3.2 为什么count初始化为1

在评论区有看到一个问题是问为什么count要初始化为1,回复是说默认情况下是整个数组,所以要加1:

[leetcode]410-分割数组的最大值

对于这个答案,我是不太认可的。

count加1的真正原因是因为最后一个子数组没有计算到count里面去,因为最后一个子数组走不到count++循环就退出了。

当循环退出的时候count来不及加1就退出了,正确的做法就是在循环结束后再自加一次,初始化为1的目的就是相当于提前加了这个1。

本文共执行69次查询,耗时0.636秒!
有空一起学习

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: