0410. Split Array Largest Sum
=============================
题目信息
--------
:题号: 0410
:难度: Hard
:主题: 连续分段、恰好 ``k`` 段、子数组和、最小化最大值
:原题: `LeetCode 0410 `_
:重点: 每段必须非空且连续、所有元素恰好属于一段、比较各段和的最大值、返回该最大值的最小可能值
题目重述
--------
给定非负整数数组 ``nums`` 和整数 ``k``,将整个数组按原顺序划分成恰好 ``k`` 个非空连续子数组。对一种划分,计算每个子数组的元素和,并取这些和中的最大值;返回所有合法划分中该最大值的最小可能值。
``nums.length`` 位于 ``[1, 1000]``,每个元素位于 ``[0, 10^6]``,``k`` 位于 ``[1, min(50, nums.length)]``。数组元素总和不会超过 32 位有符号整数范围。不能改变元素顺序,也不能遗漏或重复使用元素。
自建示例
--------
最优划分的各段大小不同:
.. code-block:: text
输入:nums = [4, 1, 7, 3, 2],k = 3
输出:7
解释:划分为 [4,1]、[7]、[3,2] 时各段和为 5、7、5,最大值为 7;任何划分都必须包含元素 7,因此答案不可能小于 7。
每个元素单独成段:
.. code-block:: text
输入:nums = [2, 9, 1],k = 3
输出:9
解释:恰好分成三段时唯一的分段方式是 [2]、[9]、[1],最大段和为 9。
二分“允许的最大段和”
----------------------
设候选上限为 ``limit``。从左到右尽量把元素放入当前段;只有加入下一个元素会超过 ``limit`` 时才切一刀。这样得到的是在该上限下所需的最少段数:每次延迟切分都让当前段尽可能长,不会增加段数。
若最少段数大于 ``k``,上限太小;若不大于 ``k``,由于数组元素非负,可以继续把某些非空段拆开,直到恰好得到 ``k`` 段。因此“可行”随 ``limit`` 单调变化,可以在 ``[max(nums), sum(nums)]`` 上二分最小可行值。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int splitArray(std::vector& nums, int k) {
long long left = 0;
long long right = 0;
for (int value : nums) {
left = std::max(left, static_cast(value));
right += value;
}
while (left < right) {
long long limit = left + (right - left) / 2;
int parts = 1;
long long current = 0;
for (int value : nums) {
if (current + value > limit) {
++parts;
current = value;
} else {
current += value;
}
}
if (parts <= k) {
right = limit;
} else {
left = limit + 1;
}
}
return static_cast(left);
}
};
代码分析
--------
贪心切段只用于判断一个 ``limit`` 是否可行,不直接声称它就是最优分段;非负元素保证段数条件具有单调性,且“至多 k 段”可细分为“恰好 k 段”。二分次数为 ``O(log sum)``,每次扫描数组,时间复杂度为 ``O(n log sum)``,额外空间为 ``O(1)``。