【LeetCode每日一题】——410.分割数组的最大值

一【题目类别】

• 贪心算法

二【题目难度】

• 困难

三【题目编号】

• 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)$

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为数组的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package GreedyAlgorithm;

/**
 * @Author: IronmanJay
 * @Description: 410.分割数组的最大值
 * @CreateTime: 2022-11-12  08:52
 */
public class p410_SplitArrayLargestSum {

    public static void main(String[] args) {
        int[] nums = {7, 2, 5, 10, 8};
        int m = 2;
        int res = splitArray(nums, m);
        System.out.println("res = " + res);
    }

    public static int splitArray(int[] nums, int k) {
        int left = 0;
        int 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 = left + (right - left) / 2;
            int splits = splits(nums, mid);
            if (splits > k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private static int splits(int[] nums, int max) {
        int splits = 1;
        int curSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (curSum + nums[i] > max) {
                splits++;
                curSum = 0;
            }
            curSum += nums[i];
        }
        return splits;
    }


}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

2. C语言版

#include

int getSplits(int* nums, int numsSize, int max)
{
	int splits = 1;
	int curSum = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (curSum + nums[i] > max)
		{
			splits++;
			curSum = 0;
		}
		curSum += nums[i];
	}
	return splits;
}

int splitArray(int* nums, int numsSize, int k)
{
	int left = 0;
	int right = 0;
	for (int i = 0; i < numsSize; i++)
	{
		right += nums[i];
		if (left < nums[i])
		{
			left = nums[i];
		}
	}
	while (left < right)
	{
		int mid = left + (right - left) / 2;
		int splits = getSplits(nums, numsSize, mid);
		if (splits > k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}
	return left;
}

/*主函数省略*/
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

十【提交结果】

1. Java语言版
   

2. C语言版