LeetCode 0410.分割数组的最大值：二分

【LetMeFly】410.分割数组的最大值：二分

力扣题目链接：https://leetcode.cn/problems/split-array-largest-sum/

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

示例 1：

输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：

输入：nums = [1,2,3,4,5], m = 2
输出：9

示例 3：

输入：nums = [1,4,4], m = 3
输出：4

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 10⁶
1 <= m <= min(50, nums.length)

方法一：二分

写一个函数check(s)，返回能否将数组nums划分为k部分且每一部分的最大值不超过s。

实现方法很简单，使用一个变量cnt来记录当前部分的元素和。

遍历数组，如果当前元素大于s，则必不可能成功划分，直接返回false。

若cnt加上当前元素超过了s，则将当前元素划分为一组（k--、cnt = 0）。

cnt加上当前元素。

遍历结束后，判断k - 1是否大于等于0。若是，则返回true，否则返回false。

有了这样的函数，我们只需要在主函数中写一个二分，枚举值mid是否能通过check。

l初始值为0，r初始值为“无穷大”（数组中所有元素之和再加一）。

当l < r时，令 $\lfloor \frac{l+r}{2} \rfloor$ 。

如果check(mid)通过了，则说明mid为一种合法分法，尝试更小的值能否成功划分（令r = mid）

否则，说明mid太小了，无法划分，尝试更大的值能否成功划分（令l = mid + 1）

二分结束后，l = r，返回l即为答案。

时间复杂度 $O(len(nums)\times \log \sum nums)$
空间复杂度 $O (1)$

AC代码

C++

class Solution {
private:bool check(vector<int>& nums, int k, int s) {int cnt = 0;for (int t : nums) {if (t > s) {return false;}if (t + cnt > s) {k--;cnt = 0;}cnt += t;}return --k >= 0;}
public:int splitArray(vector<int>& nums, int k) {int l = 0, r = accumulate(nums.begin(), nums.end(), 0) + 1;while (l < r) {int mid = (l + r) >> 1;if (check(nums, k, mid)) {r = mid;}else {l = mid + 1;}}return l;}
};

Python

# from typing import Listclass Solution:def check(self, k: int, s: int) -> bool:cnt = 0for t in self.nums:if t > s:return Falseif cnt + t > s:k -= 1cnt = 0cnt += treturn k - 1 >= 0def splitArray(self, nums: List[int], k: int) -> int:self.nums = numsl, r = 0, sum(nums) + 1while l < r:mid = (l + r) >> 1if self.check(k, mid):r = midelse:l = mid + 1return l