跳到主要内容

LeetCode 410. 分割数组的最大值

本节目标

二分允许的最大分段和，用按原顺序的贪心扫描验证最少需要多少段。

这道题是分治与二分综合框架中的拓展题。题目要求把数组按原顺序分为 k 个非空连续子数组，并最小化其中最大的子数组和；直接枚举切分位置会产生组合爆炸，应改为二分答案上界。

查看原题

题意与约束​

给定非负整数数组 nums 和整数 k，将数组分为恰好 k 个非空连续部分，返回所有部分和中的最小可能最大值。

任何答案至少是最大单个元素，否则该元素无处放置；至多是整个数组和，因为可以只分成一段。因此搜索区间自然是 [max(nums), sum(nums)]，累计量必须使用足够宽的整数类型。

朴素思路与瓶颈​

直接枚举 k - 1 个切分位置需要考察组合数量级的方案；对每种切分再计算各段和，规模稍大就不可行。固定一个最大段和上界后，是否能完成切分却可在线性时间内验证，因此适合在答案范围上二分。

固定上界时的贪心验证​

假设允许的最大段和为 limit。从左到右累加当前段：若加入下一个数仍不超过 limit，就继续放入当前段；否则必须在它之前切开，新开一段。

这个规则得到满足上界所需的最少段数：任何在更早位置切开的方案都不会让当前已累加部分容纳更多元素，只可能使用相同或更多段。若贪心最少段数仍超过 k，该上界不可行；否则可行。

为什么“不超过 k 段”已经足够​

题目最终要恰好 k 段，但数组元素非负且每段非空。若某个 limit 下贪心只用 p <= k 段，可以从任意长度至少为二的段中取一个元素单独拆出，原段和与新段和都不超过原段和，因而仍不超过 limit。重复拆分直到达到 k 段即可。

当 p < k 时，总元素数至少为 k（题目保证 k <= nums.length），所以一定存在可继续拆开的段。因此“所需最少段数不超过 k”与“能构造恰好 k 段”在本题中等价。

二分最小可行上界​

上界变大时，同一切分不会失效，可行性单调增加。二分中：

  • 所需段数不超过 k，尝试更小上界；
  • 所需段数超过 k，上界太小，向右搜索。

最终收敛到第一个可行上界，正是最小可能最大分段和。

代码实现​

两份源码使用按原顺序的贪心辅助函数计算所需段数。C++ 让上界、当前段和和中点都使用 long long，避免大值累加溢出。

C++17
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
private:
    int requiredParts(const vector<int>& nums, long long limit) {
        int parts = 1;
        long long current = 0;

        for (int number : nums) {
            if (current + number > limit) {
                parts++;
                current = number;
            } else {
                current += number;
            }
        }
        return parts;
    }

public:
    int splitArray(vector<int>& nums, int k) {
        long long left = *max_element(nums.begin(), nums.end());
        long long right = 0;
        for (int number : nums) {
            right += number;
        }

        while (left < right) {
            long long middle = left + (right - left) / 2;
            if (requiredParts(nums, middle) <= k) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return static_cast<int>(left);
    }
};

复杂度分析​

  • 时间复杂度：O(n log S)，其中 S = sum(nums) - max(nums) + 1；每次验证扫描整个数组。
  • 空间复杂度：O(1)，只维护当前段和、段数和二分边界。

易错点​

  • 把下界设为 0，让单个大元素错误通过或增加无效搜索范围。
  • 当前段恰好等于 limit 时提前切段；只有加入下一个元素会超限才需要切分。
  • 强行在验证函数里构造恰好 k 段，混淆最少段数判定与最终存在性。
  • 用 int 保存总和或中点，遇到大值总和时溢出。

模式迁移​

“最小化最大代价”常可改写为“给定上界是否可行”。后续的运输容量、任务时限和资源分配题都可沿用这条路线：先由题意给出答案上下界，再设计单调的验证函数；若验证需要按顺序做局部最优决策，贪心常是连接二分与可行性的关键。