2024.1.21力扣每日一题——分割数组的最大值

题目来源

力扣每日一题；题序：410

我的题解

方法一 动态规划+前缀和

参考官方题解

令 dp[i][j]表示将数组的前 i 个数分割为 j段所能得到的最大连续子数组和的最小值。在进行状态转移时，我们可以考虑第 j段的具体范围，即我们可以枚举 k，其中前 k个数被分割为 j−1段，而第 k+1 到第 i个数为第 j段。此时，这 j 段子数组中和的最大值，就等于 dp[k][j−1] 与 preSum(k+1,i) 中的较大值，其中 preSum(i,j)表示数组 nums 中下标落在区间 [i,j]内的数的和。

时间复杂度：O($n^{2}m$)
空间复杂度：O(nm)

public int splitArray(int[] nums, int m) {
    int n = nums.length;
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    //求前缀和
    int[] preSum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        preSum[i + 1] = preSum[i] + nums[i];
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= Math.min(i, m); j++) {
            for (int k = 0; k < i; k++) {
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], preSum[i] - preSum[k]));
            }
        }
    }
    return dp[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二 贪心+二分

参考官方题解。

时间复杂度：O(n×log(sum−maxn))
空间复杂度：O(1)

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

方法三 贪心+二分（自己的）

两个变量need和cur，分别表示需要的子数组数量和当前子数组的元素之和。
接下来，代码遍历数组nums中的每个元素num。如果cur加上num大于mid，则需要增加一个子数组，将cur重置为0。然后将num加到cur上。
最后，如果need小于等于k，则说明当前的mid满足条件，将right更新为mid；否则，将left更新为mid+1。
循环结束后，返回left作为结果。

时间复杂度：O(nlogm)。n为数组长度，m为 数组之和-数组中的最大值
空间复杂度：O(1)

public int splitArray(int[] nums, int k) {
   int left=Arrays.stream(nums).max().getAsInt();
    int right=Arrays.stream(nums).sum();
    while(left<right){
        int mid=left+((right-left)>>1);
        int need=1;
        int cur=0;
        for(int num:nums){
            if(cur+num>mid){
                need++;
                cur=0;
            }
            cur+=num;
        }
        if(need<=k)
            right=mid;
        else
            left=mid+1;
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈