D.二分查找－二分答案－最小化最大值——410. 分割数组的最大值（模板题）

题目链接：410. 分割数组的最大值（困难）

算法原理：

解法：二分查找+贪心

0ms击败100.00%

时间复杂度O(Nlogn)

①目标变量：每个数组的和（最大值）

②目标条件：将数组分成k份，找一个数当每个数组和的最大值，这个数要最小化

③转换逻辑：是否能将nums分割为≤k个子数组，且每个子数组的和都≤mid

具体步骤：

①确定边界：

left：数组中最大元素，因为每个子数组至少一个元素，最大值不可能比最大元素小

right：数组元素和，因为k=1时，只能是整个数组的和

②确定二分模型： 分的段数 ↑ 元素和的最大值 ↓ ，呈负相关单调，由于是找最小的最大值，因此采用最左端点模型

③check方法设计：这里采用贪心策略来验证：在给定最大子数组和限制mid下，能否将数组分割成不超过k个连续子数组

贪心的核心想法：尽可能把更多元素塞进当前子数组，找到满足条件的最少元素数量，如果这个数量≤k，则说明可行

1.初始化：

子数组计数cnt=1，因为数组至少是一个子数组

当前子数组累加和sum=0

2.遍历数组：对于每个数x

如果sum+x≤mid，将x加入当前子数组，继续下一个元素

否则就新开个数组，新数组和重置为x

再在中间加个判断：如果子数组已经到了k个，那么直接返回false

3.返回true

答疑

Q1：那要是k太大了，分不成k组呢？那这个贪心不就错了吗？

题目已经明确说明了1 <= k <= min(50, nums.length)，因此不可能存在这种情况，贪心没问题

Java代码：

class Solution { public int splitArray(int[] nums, int k) { int left=0,right=0; for(int x:nums){ left=Math.max(left,x); right+=x; } while(left<right){ int mid=left+(right-left)/2; if(!check(mid,nums,k)) left=mid+1; else right=mid; } return left; } //判断是否能将nums分割为≤k个子数组，且每个子数组的和都≤mid private boolean check(int mid,int[] nums, int k){ //当前子数组累加和 int sum=0; //子数组计数，初始为1（至少一个子数组） int cnt=1; for(int x:nums){ if(sum+x<=mid){ sum+=x; continue; } if(cnt==k) return false; cnt++; sum=x; } return true; } }