LeetCode 410 - 分割数组的最大值

今天要聊的题是 LeetCode 410：分割数组的最大值（Split Array Largest Sum）。这题的核心是——如何在把数组拆成 k 段之后，让这些段的“最大和”尽可能小。换句话说，这是一道非常经典的“二分 + 贪心”混合问题。看起来像是要枚举所有分法，但实际上我们可以通过“最大和上限”来二分搜索答案，找到最优解。这类题在项目中也挺常见，比如你要把一批任务分配给 k 台服务器，每台机

Swift社区

987人浏览 · 2025-10-29 20:25:22

Swift社区 · 2025-10-29 20:25:22 发布

在这里插入图片描述

文章目录

摘要

今天要聊的题是 LeetCode 410：分割数组的最大值（Split Array Largest Sum）。
这题的核心是——如何在把数组拆成 k 段之后，让这些段的“最大和”尽可能小。

换句话说，这是一道非常经典的“二分 + 贪心”混合问题。看起来像是要枚举所有分法，但实际上我们可以通过“最大和上限”来二分搜索答案，找到最优解。

这类题在项目中也挺常见，比如你要把一批任务分配给 k 台服务器，每台机器的任务量不能太悬殊，我们就希望找到“最平衡”的那种分法。

描述

题目是这样说的：

给定一个非负整数数组 nums 和一个整数 k，我们需要把 nums 拆成 k 个非空连续子数组，使得这 k 个子数组的“和的最大值”尽量小。

返回这个最小的“最大和”。

比如：

输入：nums = [7,2,5,10,8], k = 2
输出：18

这里最优的拆法是 [7,2,5] 和 [10,8]。
第一个子数组的和是 14，第二个是 18，所以“最大和”是 18。
而且这 18 是所有拆法中最小的可能值。

题解答案

这题的暴力解法显然行不通，因为所有拆法的组合太多了。
一个更聪明的思路是：
我们可以“假设”当前能接受的最大和是 x，然后去判断能不能把数组拆成 ≤ k 段，使得每段的和都 ≤ x。

如果能做到，那说明 x 还可以更小；
如果做不到，那说明 x 太小了，得放宽。

这样我们就能用“二分法”去搜索最小可行的 x。
听起来像 DP，但其实用贪心就能实现判断逻辑。

题解代码分析

下面是完整的 Swift 代码，可以直接在 LeetCode Playground 或 Xcode 里运行：

import Foundation

class Solution {
    func splitArray(_ nums: [Int], _ k: Int) -> Int {
        var left = nums.max() ?? 0   // 下界：至少要能装得下最大的单个元素
        var right = nums.reduce(0, +) // 上界：所有元素相加（全部不拆的情况）
        var result = right

        // 二分查找最小的“最大子数组和”
        while left <= right {
            let mid = (left + right) / 2
            if canSplit(nums, k, mid) {
                result = mid
                right = mid - 1 // 尝试更小的上限
            } else {
                left = mid + 1 // 当前上限太小，不够装
            }
        }
        return result
    }

    // 判断能否用 <= k 段来满足“每段和 ≤ maxSum”
    private func canSplit(_ nums: [Int], _ k: Int, _ maxSum: Int) -> Bool {
        var count = 1
        var 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 设为 nums 中的最大值（任何分法都得能装下最大的元素）。
- right 是数组总和（最极端的情况：不拆分）。
二分搜索逻辑：
- 每次取 mid 作为当前假设的“最大和上限”。
- 调用 canSplit() 判断在这个上限下能不能拆成 k 段。
- 如果能，那我们试试看更小的上限；
- 如果不能，那说明这上限太紧，得放大。
canSplit 函数：
用一个简单的贪心法，从左到右累加，一旦超出 maxSum 就“另开一段”。
如果段数超过 k，说明当前上限不行。

这段代码思路非常简洁，逻辑清晰，不需要 DP 就能在 O(n log(sum)) 的时间内完成判断。

示例测试及结果

我们来手动测试几个例子。

let solution = Solution()

print(solution.splitArray([7,2,5,10,8], 2))  // 输出: 18
print(solution.splitArray([1,2,3,4,5], 2))   // 输出: 9
print(solution.splitArray([1,4,4], 3))       // 输出: 4