二分法解决分割数组的最大值问题：从思路到实践-育师

创作灵感

在刷力扣题的过程中，遇到 “分割数组的最大值” 这道题，其巧妙的二分法运用让我眼前一亮。作为技术学习路上的探索者，想通过梳理解题思路、剖析代码逻辑，把二分法在这类 “最大化最小值” 问题里的应用吃透，于是有了这篇技术笔记。

一、题目剖析：目标与挑战

给定非负整数数组nums和整数k，要把数组分成k个非空连续子数组，让这k个子数组各自和的最大值最小，并返回该最小值。比如nums = [7,2,5,10,8]，k = 2时，最优分割是[7,2,5]和[10,8]，最大和为18。核心挑战是在众多分割方式里，高效找到使最大和最小的那个方案。

二、解题思路：二分法的巧妙应用

（一）算法选择逻辑

这类 “在可能的取值范围内找最优解，且可通过判断条件缩小范围” 的问题，很适合用二分法。关键是确定合理的查找范围，以及能快速验证 “某个中间值是否可行” 的判断函数。对于本题，分割后子数组和的最大值，最小不会小于数组里的最大值（单个元素无法再分割更小），最大不会超过数组元素的总和（不分割整个数组的情况）。所以二分查找的范围就确定在[max(nums), sum(nums)]。

（二）具体执行步骤

确定边界：遍历数组，找到left（数组最大值）和right（数组总和），作为二分查找的初始范围。
二分查找：取中间值mid，判断能否将数组分割成k个子数组，且每个子数组和不超过mid。若可以，尝试缩小右边界（找更小的最大值）；若不行，增大左边界。
验证函数：canSplit函数里，遍历数组累加元素，当累加和超过mid时，新起一个子数组，同时统计子数组数量。若数量超过k，说明mid太小不可行；反之可行。

三、代码实现（C++

class Solution { public: int splitArray(vector<int>& nums, int k) { // 确定二分查找的左右边界 int left = 0, right = 0; for (int num : nums) { left = max(left, num); // 左边界为数组元素最大值 right += num; // 右边界为数组元素总和 } // 二分查找最小的最大和 while (left < right) { int mid = left + (right - left) / 2; // 防止整数溢出 if (canSplit(nums, k, mid)) { right = mid; // 可行则尝试更小值，调整右边界 } else { left = mid + 1; // 不可行则增大左边界 } } return left; // 最终左边界即为答案 } // 验证函数：判断能否分割成k个子数组，且每个子数组和不超maxSum bool canSplit(vector<int>& nums, int k, int maxSum) { int count = 1; // 子数组数量，至少1个 int currentSum = 0; // 当前子数组累加和 for (int num : nums) { if (currentSum + num > maxSum) { // 超过maxSum，新起子数组 count++; currentSum = num; if (count > k) { // 子数组数量超k，返回false return false; } } else { currentSum += num; // 加入当前子数组 } } return count <= k; // 数量符合要求则返回true } };

四、代码解析

边界确定：通过遍历数组，left被更新为数组最大值（保证每个子数组至少包含最大元素，是最小可能的最大和下限），right累加得到总和（是不分割时的最大和上限）。
二分循环：用left + (right - left) / 2计算mid避免整数溢出。根据canSplit的返回值调整边界，逐步逼近最优解。
canSplit函数：遍历数组模拟分割过程，累加和超maxSum时新建子数组，同时检查子数组数量是否超限，快速验证mid的可行性，时间复杂度为O(n)（n是数组长度）。

五、复杂度分析

时间复杂度：二分查找的时间复杂度是O(log S)（S是数组总和与最大值的差值），每次二分调用canSplit是O(n)，所以整体是O(n log S)，对于数组长度n来说，效率较高。
空间复杂度：仅用了常数级别的额外空间（几个变量），空间复杂度为O(1)。

六、测试用例验证

以示例nums = [7,2,5,10,8]，k = 2为例：

初始left = 10（数组最大值），right = 32（总和7+2+5+10+8=32）。
第一次mid = (10+32)/2 = 21，canSplit验证：累加7+2+5=14 ≤21，接着加10得24>21，新起子数组，此时子数组数量2，未超k=2，但10+8=18 ≤21，最终count=2 ≤2，返回true，调整right=21。
继续二分，直到left = right = 18，得到正确结果。