来源:力扣 (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,计算出来符合条件的子数组为:
1 |
[7,2,5,10] [8] |
子数组 m 的个数刚好等于 2,设置 right=mid-1=20,再计算 mid=15,符合条件的数组:
1 |
[7,2,5] [10] [8] |
子数组个数为 3,大于要求的 2,设置 left=mid+1=16,计算 mid=(16+20)/2=18,符合条件的数组:
1 |
[7,2,5] [10] [8] |
子数组个数为 2,满足题目要求,设置 right=mid-1=17,计算 mid=(16+17)/2=16,符合条件的数组:
1 |
[7,2,5] [10] [8] |
子数组个数为 3,大于要求的 2,设置 left=mid+1=17,计算 mid=(17+17)/2=17,符合条件的数组:
1 |
[7,2,5] [10,8] |
子数组个数还是 3,大于要求的 2,设置 left=mid+1=18,此时 left 大于 right(17),遍历结束,返回 18 。
三、示例代码
3.1 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Solution { public: int splitArray(vector<int> &nums, int m) { size_t i; int count = 0; long left = nums[0], right = 0, mid, sum; // 确定左右边界 for (i = 0; i < nums.size(); i++) { right += nums[i]; left = left < nums[i] ? nums[i] : left; } while (left <= right) { mid = (left + right) / 2; sum = 0; count = 1; // count 要初始化为 1 // 遍历所有的和 for (i = 0; i < nums.size(); i++) { // 和超出了,重新计算下一个子数组 if (sum + nums[i] > mid) { sum = nums[i]; count ++; } else { sum += nums[i]; } } if (count > m) { left = mid + 1; } else { right = mid - 1; } } return (int)left; } }; |
3.2 为什么 count 初始化为 1
在评论区有看到一个问题是问为什么 count 要初始化为 1,回复是说默认情况下是整个数组,所以要加 1:
对于这个答案,我是不太认可的。
count 加 1 的真正原因是因为最后一个子数组没有计算到 count 里面去,因为最后一个子数组走不到 count++循环就退出了。
1 2 3 |
cnt=0 cnt=1 循环退出 ↓ ↓ ↓ [] [7,2,5] [10, 8] |
当循环退出的时候 count 来不及加 1 就退出了,正确的做法就是在循环结束后再自加一次,初始化为 1 的目的就是相当于提前加了这个 1 。
评论