Hard

题目描述

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

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

返回这个最小的最大值。

示例 1：

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

示例 2：

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

提示：

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

解题思路

这道题有两种经典解法：动态规划和二分搜索。我们重点介绍更优的二分搜索解法。

二分搜索解法（推荐）： 核心思想是二分答案。我们观察到答案的范围在 [max(nums), sum(nums)] 之间，其中下界是数组中的最大值（至少需要一个子数组包含它），上界是整个数组的和（只分成一个子数组）。

对于给定的最大值限制 mid，我们可以贪心地检查能否将数组分成不超过 k 个子数组：从左到右遍历，尽可能多地将元素加入当前子数组，直到加入下一个元素会超过 mid，然后开始新的子数组。

如果能分成不超过 k 个子数组，说明 mid 可行，尝试更小的值；否则需要更大的值。

动态规划解法： 定义 dp[i][j] 表示将前 i 个元素分成 j 个子数组的最小最大值。状态转移方程为：dp[i][j] = min(max(dp[p][j-1], sum(p+1, i))) 对所有可能的分割点 p。

时间复杂度：二分搜索 O(n×log(sum))，动态规划 O(n²×k)。对于此题的数据范围，二分搜索更优。

代码实现

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int left = *max_element(nums.begin(), nums.end());
        int right = accumulate(nums.begin(), nums.end(), 0);
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
private:
    bool canSplit(vector<int>& nums, int k, int maxSum) {
        int count = 1;
        int currentSum = 0;
        
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
                if (count > k) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }
};

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def canSplit(maxSum):
            count = 1
            currentSum = 0
            
            for num in nums:
                if currentSum + num > maxSum:
                    count += 1
                    currentSum = num
                    if count > k:
                        return False
                else:
                    currentSum += num
            return True
        
        left, right = max(nums), sum(nums)
        
        while left < right:
            mid = (left + right) // 2
            if canSplit(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int SplitArray(int[] nums, int k) {
        int left = nums.Max();
        int right = nums.Sum();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CanSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private bool CanSplit(int[] nums, int k, int maxSum) {
        int count = 1;
        int currentSum = 0;
        
        foreach (int num in nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
                if (count > k) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

var splitArray = function(nums, k) {
    function canSplit(maxSum) {
        let count = 1;
        let currentSum = 0;
        
        for (let num of nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
                if (count > k) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }
    
    let left = Math.max(...nums);
    let right = nums.reduce((sum, num) => sum + num, 0);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canSplit(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
二分搜索O(n × log(sum))O(1)
动态规划O(n² × k)O(n × k)

其中 n 是数组长度，sum 是数组元素总和。二分搜索解法在时间和空间上都更优秀。

相关题目