410.分割数组的最大值

【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] <= 106
• 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时，令$mid = \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 List

class Solution:
    def check(self, k: int, s: int) -> bool:
        cnt = 0
        for t in self.nums:
            if t > s:
                return False
            if cnt + t > s:
                k -= 1
                cnt = 0
            cnt += t
        return k - 1 >= 0

    def splitArray(self, nums: List[int], k: int) -> int:
        self.nums = nums
        l, r = 0, sum(nums) + 1
        while l < r:
            mid = (l + r) >> 1
            if self.check(k, mid):
                r = mid
            else:
                l = mid + 1
        return l

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135728821