LC410. 分割数组的最大值【贪心 + 二分答案】

张开发
• 2026/4/11 20:55:44 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LC410. 分割数组的最大值【贪心 + 二分答案】
410. 分割数组的最大值给定一个非负整数数组nums和一个整数k你需要将这个数组分成k个非空的连续子数组使得这k个子数组各自和的最大值最小。返回分割后最小的和的最大值。子数组是数组中连续的部分。示例 1输入nums [7,2,5,10,8], k 2 输出18 解释 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18在所有情况中最小。示例 2输入nums [1,2,3,4,5], k 2 输出9示例 3输入nums [1,4,4], k 3 输出4提示1 nums.length 10000 nums[i] 1061 k min(50, nums.length)思路这道题的经典解法是**“二分查找 贪心算法”**。遇到“求最大值的最小值”这类字眼通常都可以优先考虑二分法。核心解题思路锁定答案范围二分边界无论怎么分割子数组和的最大值最小不会低于数组中的最大元素相当于切成最多份k nums.length最大不会超过数组的元素总和相当于切成1份k 1。这就是二分查找的上下界。贪心验证Check 函数假设当前我们猜想的最大和是mid我们如何验证它是否合法 我们从左到右遍历数组依次累加元素。如果加上当前元素后超过了mid说明当前子数组必须在这里截断开启下一个子数组。遍历结束后统计切出的子数组数量count。调整二分方向如果count k说明切的份数太多了意味着我们设定的mid太小需要增大下界left mid 1。如果count k说明切的份数刚好或者还可以更少意味着mid是一个合法的解但可能还有更小的解所以缩小上界继续逼近right mid。// 注意到题目中的最小值最大 - 二分答案classSolution{public:intsplitArray(vectorintnums,intk){intl0,r0;for(autox:nums){rx;lmax(l,x);}coutl, r: l rendl;functionbool(int)check[](intmid){intcnt1,cur0;for(autox:nums){if(curxmid)cnt,curx;elsecurx;}coutmid: mid cnt: cntendl;returncntk;};while(lr){intmidlr1;if(check(mid))rmid;elselmid1;}returnl;}};

更多文章