LeetCode 410. 分割数组的最大值

Categories:

题目描述
思路分析
1. 解法一：二分答案 + 贪心校验（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 410. 分割数组的最大值

思路分析

解法一：二分答案 + 贪心校验（推荐）

核心思路：

答案的范围是 [max(nums), sum(nums)]：最小可能是最大单个元素（每组一个元素），最大是所有元素之和（只有一组）。

对这个范围进行二分，每次取中间值 mid 作为”子数组元素和的上限”。

用贪心 check(mid) 判断：在每个子数组和不超过 mid 的条件下，贪心地尽量往当前组塞元素，统计需要的最少分组数。

如果最少分组数 <= m，说明 mid 可以满足条件，尝试缩小上限；否则增大 mid。

复杂度分析：

时间复杂度：O(n × log(sum - max))，其中 n 是数组长度，二分范围是 sum - max。

空间复杂度：O(1)，只使用常数额外空间。

class Solution {

    public int splitArray(int[] nums, int m) {
        // 二分答案的左右边界
        long left = 0, right = 0;
        for (int num : nums) {
            // 左边界取数组最大值
            left = Math.max(left, num);
            // 右边界取数组总和
            right += num;
        }

        while (left < right) {
            long mid = left + (right - left) / 2;
            // 判断以 mid 为上限能否将数组分成不超过 m 组
            if (check(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return (int) left;
    }

    // 贪心校验：在子数组和不超过 limit 的条件下，统计最少需要几组
    private boolean check(int[] nums, long limit, int m) {
        // 当前组的累计和
        long currentSum = 0;
        // 所需分组数，初始已有第一组
        int count = 1;
        for (int num : nums) {
            // 加入当前元素后超过上限，则新开一组
            if (currentSum + num > limit) {
                count++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        return count <= m;
    }
}

func splitArray(nums []int, m int) int {
    // 二分答案的左右边界
    left, right := 0, 0
    for _, num := range nums {
        // 左边界取数组最大值
        if num > left {
            left = num
        }
        // 右边界取数组总和
        right += num
    }

    for left < right {
        mid := left + (right-left)/2
        // 判断以 mid 为上限能否将数组分成不超过 m 组
        if check(nums, mid, m) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

// check 贪心校验：在子数组和不超过 limit 的条件下，统计最少需要几组
func check(nums []int, limit, m int) bool {
    // 当前组的累计和
    currentSum := 0
    // 所需分组数，初始已有第一组
    count := 1
    for _, num := range nums {
        // 加入当前元素后超过上限，则新开一组
        if currentSum+num > limit {
            count++
            currentSum = num
        } else {
            currentSum += num
        }
    }
    return count <= m
}

解法二：动态规划

核心思路：

定义 dp[i][j] 表示将前 i 个元素分成 j 组时，各子数组元素和的最大值的最小值。

状态转移：枚举最后一组的起点 k，dp[i][j] = min(max(dp[k][j-1], sum(k+1..i))) 。

利用前缀和数组快速计算区间和。

复杂度分析：

时间复杂度：O(n² × m)，其中 n 是数组长度，m 是分组数。

空间复杂度：O(n × m)，用于存储 dp 数组。

class Solution {

    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        // 构建前缀和数组
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        // dp[i][j] 表示前 i 个元素分成 j 组时的最大子数组和最小值
        long[][] dp = new long[n + 1][m + 1];
        for (long[] row : dp) {
            java.util.Arrays.fill(row, Long.MAX_VALUE / 2);
        }
        dp[0][0] = 0;

        for (int j = 1; j <= m; j++) {
            for (int i = 1; i <= n; i++) {
                // 枚举最后一组的起点 k
                for (int k = j - 1; k < i; k++) {
                    // 最后一组的区间和
                    long lastSum = prefix[i] - prefix[k];
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], lastSum));
                }
            }
        }

        return (int) dp[n][m];
    }
}

func splitArray(nums []int, m int) int {
    n := len(nums)
    // 构建前缀和数组
    prefix := make([]int, n+1)
    for i, num := range nums {
        prefix[i+1] = prefix[i] + num
    }

    // dp[i][j] 表示前 i 个元素分成 j 组时的最大子数组和最小值
    const inf = math.MaxInt32
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
        for j := range dp[i] {
            dp[i][j] = inf
        }
    }
    dp[0][0] = 0

    for j := 1; j <= m; j++ {
        for i := 1; i <= n; i++ {
            // 枚举最后一组的起点 k
            for k := j - 1; k < i; k++ {
                // 最后一组的区间和
                lastSum := prefix[i] - prefix[k]
                val := max(dp[k][j-1], lastSum)
                if val < dp[i][j] {
                    dp[i][j] = val
                }
            }
        }
    }

    return dp[n][m]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	二分答案、贪心
1011. 在 D 天内送达包裹的能力	中等	二分答案、贪心
1231. 分享巧克力	困难	二分答案、贪心
2064. 分配给商店的最多商品的最小值	中等	二分答案
1760. 袋子里最少数目的球	中等	二分答案
378. 有序矩阵中第 K 小的元素	中等	二分查找
719. 找出第 K 小的数对距离	困难	二分答案、滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/99466209