【LeetCode每日一题】410. 分割数组的最大值-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode每日一题】410. 分割数组的最大值。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2024-1-21

410. 分割数组的最大值

【LeetCode每日一题】410. 分割数组的最大值,LeetCode,leetcode,算法,职场和发展

思路：二分查找+贪心

利用二分查找法和贪心算法来求解将数组分割为m个非空连续子数组，使得每个子数组的和的最大值最小

首先，我们需要确定二分查找的左右边界。左边界left初始化为数组中的最大值，右边界right初始化为数组所有元素的总和。
然后，我们使用二分查找法在左右边界之间查找满足条件的最小子数组和。
在每次迭代中，我们计算中间值mid，然后调用check函数判断以mid为目标值是否能将数组nums分割成不超过m个子数组。如果能，则将右边界更新为mid，因为我们要寻找更小的子数组和。如果不能，则将左边界更新为mid + 1，因为mid不满足条件，我们需要尝试更大的值。
当左边界left不小于右边界right时，二分查找结束，最终的结果即为左边界的值。
最后，返回左边界的值作为最小子数组和。

public int splitArray(int[] nums, int m) {
    int left = 0, right = 0;
    // 初始化左右边界
    for (int i = 0; i < nums.length; i++) {
        right += nums[i];
        if (left < nums[i]) {
            left = nums[i];
        }
    }
    
    // 使用二分查找法寻找最小的子数组和
    while (left < right) {
        int mid = (right - left) / 2 + left;
        if (check(nums, mid, m)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    // 返回最小的子数组和
    return left;
}

public boolean check(int[] nums, int x, int m) {
    int sum = 0;
    int cnt = 1;
    // 统计满足条件的子数组个数
    for (int i = 0; i < nums.length; i++) {
        if (sum + nums[i] > x) {
            // 当前元素加上之后超过了目标值，需要分割出一个新的子数组
            cnt++;
            sum = nums[i];
        } else {
            // 将当前元素加入到当前子数组中
            sum += nums[i];
        }
    }
    
    // 判断最终的子数组个数是否小于等于目标个数
    return cnt <= m;
}