LeetCode410-分割数组的最大值

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/split-array-largest-sum/

中文链接：https://leetcode-cn.com/problems/split-array-largest-sum/

题目详述

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

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

题目详解

  • 如果给定子数组和的上限 cap 满足则要求，那么满足 x >= cap 的 x 均满足要求，即在这一条件上，具有有界性，可以运用二分查找，查找第一个满足要求的 cap。
  • 对于每一个 cap，遍历数组，统计子数组之和小于等于容量 cap 的数组个数。
    • 如果它小于等于 m，说明用 cap 能进行分割，r = mid。
    • 如果它大于 m，说明不用 cap 能进行分割，l = mid + 1。
  • 初始的上界和下界分别为 sum、max。其中 sum 代表数组元素和，即分割为 1 个数组（自身），max 代表数组元素最大值，即分割为单个元素。
  • 注意为了防止溢出，数组元素和相关变量为 long 类型。
  • 时间复杂度为 O(nlog(sum))，其中 sum 为数组元素和。
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
public class LeetCode_00410 {

    public int splitArray(int[] nums, int m) {
        long l = 0, r = 0;
        for (int x : nums) {
            l = Math.max(l, x);
            r += x;
        }
        while (l < r) {
            long mid = l + r >>> 1;
            if (check(nums, m, mid)) r = mid;
            else l = mid + 1;
        }
        return (int) r;
    }

    private boolean check(int[] nums, int m, long cap) {
        int cnt = 1;
        long tot = 0;
        for (int x : nums) {
            tot += x;
            if (tot > cap) {
                ++cnt;
                tot = x;
            }
        }
        return cnt <= m;
    }
}