Leetcode 2025-01-21 题目分享

410. 分割数组的最大值

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 10^6
1 <= k <= min(50, nums.length)

思路

题面很简洁，只需要注意到’最大值最小’==>二分。
二分是最直接解决“最大值最小，最小值最大”等一系列极值问题的。

常见两种思路：1）二分所要求的答案 2）二分关键的中间值
这题很明显就是二分答案：

单调性：如果最大值为v，可以分成t个子数组（t<=k）；

那么最大值比v大时，分成的子数组数量一定小于等于t。（因为每个子数组能包含的值更大了，一些数值较小的子数组可以合并到其他子数组）

上界：最大的和，肯定是整个数组的和（此时t=1，只有一个子数组）。

下界：数组中元素最大值（此时每个元素作为一个子数组）。
每次二分得到一个最大值，我们要让这个最大值尽可能小。

check函数中遍历数组，依次累加。

等累加值超出当前二分的最大值时，说明需要重新再开一个子数组。

看最后子数组的数量是不是小于k即可。

代码

function splitArray(nums: number[], k: number): number {
    let sum = 0, max = 0;
    nums.forEach(x => {
        sum += x;
        max = max > x ? max : x;
    });
    let check = (mid:number):boolean => {
        let t = 1, cur = 0;
        nums.forEach(v => {
            cur += v;
            if (cur > mid){
                cur = v;
                t++;
            }
        });
        return t <= k;
    };
    let l = max, r = sum;
    while (l <= r){
        let mid = l+r >> 1;
        if (check(mid)) r = mid-1;
        else l = mid+1;
    }
    return l;
};

复杂度分析

时间：O(n * log ∑nums)。
空间：O(1)。