LeetCode第410题：分割数组的最大值

难度：困难

题目链接：LeetCode第410题

题目描述

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

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

示例 1：

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

示例 2：

输入：nums = [1,2,3,4,5], k = 2
输出：9

示例 3：

输入：nums = [1,4,4], k = 3
输出：4

提示：

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

解题思路

这道题目可以使用二分查找来解决，核心思路是：

1. 确定二分查找的范围：
   • 左边界是数组中的最大值
   • 右边界是数组所有元素的和
2. 对于每个中间值，检查是否可以将数组分成k个子数组，且每个子数组的和不超过该值
3. 根据检查结果调整二分查找的范围

算法流程

1. 初始化二分查找范围：

   • left = max(nums)
   • right = sum(nums)

2. 二分查找过程：

   • mid = (left + right) / 2
   • 检查是否可以用mid作为子数组和的上限，将数组分成k个子数组
   • 如果可以，说明mid可能偏大，尝试减小
   • 如果不可以，说明mid太小，需要增大

3. 检查函数实现：

   • 贪心地将数组划分为尽可能多的子数组
   • 每个子数组的和不超过mid
   • 统计划分出的子数组个数是否小于等于k

代码实现

C# 实现

public class Solution {
    public int SplitArray(int[] nums, int k) {
        // 初始化二分查找范围
        long left = nums.Max();
        long right = nums.Sum(x => (long)x);
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            
            // 检查是否可以用mid作为上限分割成k个子数组
            if (CanSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return (int)left;
    }
    
    private bool CanSplit(int[] nums, int k, long maxSum) {
        int count = 1;
        long currentSum = 0;
        
        foreach (int num in nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
                
                if (count > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        
        return true;
    }
}

Python 实现

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def canSplit(maxSum: int) -> bool:
            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 = max(nums)
        right = sum(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if canSplit(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

C++ 实现

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

执行结果

C# 实现

• 执行用时：84 ms
• 内存消耗：36.4 MB

Python 实现

• 执行用时：36 ms
• 内存消耗：15.1 MB

C++ 实现

• 执行用时：0 ms
• 内存消耗：7.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	84 ms	36.4 MB	代码结构清晰，性能一般
Python	36 ms	15.1 MB	代码简洁，性能中等
C++	0 ms	7.2 MB	性能最优，内存占用最小

代码亮点

1. 🎯 巧妙运用二分查找解决最优化问题
2. 💡 使用贪心策略验证分割方案
3. 🔍 细致的边界条件处理
4. 🎨 各语言实现保持了代码的简洁性

常见错误分析

1. 🚫 二分查找边界设置错误
2. 🚫 整数溢出处理不当
3. 🚫 贪心策略实现不正确
4. 🚫 未考虑特殊输入情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
二分查找+贪心	O(nlog(sum))	O(1)	实现简单，空间效率高	不是严格O(n)的解法
动态规划	O(n²k)	O(nk)	可以得到所有状态	时间和空间复杂度高

相关题目

• LeetCode 1011. 在 D 天内送达包裹的能力 - 中等
• LeetCode 1231. 分享巧克力 - 困难

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第410题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！