引入
之前在周赛遇到5438. 制作 m 束花所需的最少天数：
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
示例 1：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _] // 只能制作 1 束花
2 天后：[x, _, _, _, x] // 只能制作 2 束花
3 天后：[x, _, x, _, x] // 可以制作 3 束花，答案为 3
今天的每日一题又遇到了：410. 分割数组的最大值
这两道题看似都可以用回溯来解，实际上回溯不太好做剪枝，不做剪枝的回溯和暴力法没有什么区别。
这类求数组里的某一个值或者某一部分和的最大、最小值，往往可以用二分法。
以前的二分法似乎应用场景局限在了已排序数组的查找上，这种思想是不对的。
来说下这种另类的二分法的解题步骤：
- 找到边界值，即二分的left和right的值。
- 根据left和right获取mid。
- 根据mid遍历数组，判断是否符合条件，并收缩left或者right的边界值。
二分法题解：制作 m 束花所需的最少天数
二分查找的步骤如下：
- 将花成熟的天数放进容器中，排序（排序的目的其实就是为了找到二分的left和right值）
- 将排序后的容器的下标作为操作对象，根据容器的值的比较结果做为依据进行二分查找。即left=0,rgiht=nums.length-1，找到中间的mid对应的天数。
- 依据mid对应的天数做以此遍历比较，看看当前的天数是否满足要求。注意：这个情景下的二分查找找到合适的值时不能直接返回，因为可能有更小的天数时，符合要求的总花束与当前的花束相等（总花枝不等）
import java.util.Arrays;
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
int[] arr=new int[bloomDay.length];
for (int i=0;i<bloomDay.length;i++){
arr[i]=bloomDay[i];
}
Arrays.sort(arr);
int left=0,right=bloomDay.length-1;
int ans=-1;
while (left<=right){
int mid=(left+right)>>>1;
int limit=arr[mid];
if (isEligible(bloomDay,limit,k)>=m){
//满足要求,说明mid大了
ans=limit;
right=mid-1;
}else{
left=mid+1;
}
}
return ans;
}
public int isEligible(int[] bloomDay,int limit,int k){
int tmp=0;
int count=0;
for (int i:bloomDay){
if (i<=limit) tmp++;
else tmp=0;
if (tmp==k){
count++;
tmp=0;
}
}
return count;
}
}
二分法题解：分割数组的最大值
public class Solution {
public int splitArray(int[] nums, int m) {
int N = nums.length;
if (N == 0) return 0;
int left = nums[0], right = 0;
//计算左边界和右边界
for (int i : nums) {
right += i;
if (left < i) left = i;
}
//二分法查找最小值，这和养花的题一样！
while (left < right) {
int mid = (left + right) >>> 1;
if (helper(mid, nums, m)) {
right=mid;
}else left=mid+1;
}
return left;
}
public boolean helper(int mid, int[] nums, int m) {
int count = 1;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum > mid) {
count++;
sum = nums[i];
}
}
return count <= m;
}
}
二分法题解：两球之间的磁力
题目：5489.两球之间的磁力，不做赘述。
这道题我一开始使用的是dp，但是使用dp会需要三层循环，时间复杂度超了。
import java.util.*;
public class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int n=position.length;
//dp[j][k]，表示第k个新的球放置在j的位置上时的最大最小磁力。
int[][] dp=new int[n][m+1];
//初始值
for (int j=0;j<n;j++){
dp[j][1]=Integer.MAX_VALUE;
}
for (int i=1;i<=m;i++){ //i个球
for (int j=0;j<n;j++){
for (int k=1;k+j<n;k++){
dp[j+k][i]=Math.max(dp[j+k][i],Math.min(dp[j][i-1],position[j+k]-position[j]));
}
}
}
return dp[n-1][m];
}
}
这道题的最佳解法是使用二分法来做题解，也就是求出一个间距mid，然后判断如果使用这个mid，是否能够塞下m个球。
import java.util.*;
public class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
//low和high表示每个球的间隔的最小值和最大值
int low = 1;
int high = (position[position.length - 1] - position[0]) / (m - 1);
//二分法
int ans = 0;
while (low <= high) {
int mid = (low + high) >>> 1;
if (isFit(position, m, mid)) {
ans = mid;
low = mid + 1;
} else {
//说明间隔太大，不足以放下这么多球
high = mid - 1;
}
}
return ans;
}
/**
* 判断以disntance为距离能否塞下m个球
*
* @param position 能够放球的桶的位置
* @param m 球的个数
* @param distance 每个球的最小间距
* @return
*/
public boolean isFit(int[] position, int m, int distance) {
int begin = position[0];
m--;//第一个球放begin的位置
for (int i = 0; i < position.length; i++) {
if (position[i] - begin >= distance) {
m--;
begin = position[i];
}
}
return m <= 0;
}
}
