【二分查找】分割数组的最大值

题目

410. 分割数组的最大值

---

给定一个非负整数数组 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^6
• 1 <= m <= min(50, nums.length)

解题

方法一：二分查找

思路

这题看似很难，感觉要上动态规划，但其实仔细读题就会发现这题和【二分查找】在 D 天内送达包裹的能力是一模一样的，甚至把解题代码复制过来改一下函数名就可以过。

代码

class Solution {
    int f(vector<int>& nums, int sum) {
        int curr = 0, split = 0;
        for (int& num : nums) {
            if (curr + num >= sum) {
                curr = curr + num > sum ? num : 0;
                ++split;
            } else curr += num;
        }
        if (curr > 0) ++split;
        return split;
    }

public:
    int splitArray(vector<int>& nums, int k) {
        int left = 0, right = 0;
        for (int& num : nums) {
            left = max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (f(nums, mid) <= k) right = mid;
            else left = mid + 1; 
        }
        return left;
    }
};

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(nums, k, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    boolean check(int[] nums, int k, int sum) {
        int curr = 0, split = 0;
        for (int num : nums) {
            if (curr + num >= sum) {
                curr = curr + num > sum ? num : 0;
                if (++split > k) return false;
            } else curr += num;
        }
        if (curr > 0) ++split;
        return split <= k;
    }
}