基本概念
将最值问题转换为判定
与二分查找的区别
二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案
如何判断一个题是不是用二分答案做的
1、答案在一个区间内（一般情况下，区间会很大，暴力超时）
2、直接搜索不好搜，但是容易判断一个答案可行不可行
3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。
此外，可能还会有一个典型的特征：求...最大值的最小 、 求...最小值的最大。
1、求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid）
2、同样，求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid）
例题
875. 爱吃香蕉的珂珂
题目
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
示例 1：
输入：piles = [3,6,7,11], h = 8 输出：4
示例 2：
输入：piles = [30,11,23,4,20], h = 5 输出：30
示例 3：
输入：piles = [30,11,23,4,20], h = 6 输出：23
提示：
1 <= piles.length <= 104piles.length <= h <= 1091 <= piles[i] <= 109
思路：
比如：
- [6,4 ,5,2,4,3]，离开20h
- 假如说速度是5根/1h
- 1)6->1
- 2)1->0
- 然后休息
- 3)4->0
- 休息
- 有富余的时间就休息了，没富余时间继续吃下一堆
- 推下来5达标满足
- 然后推下来4也达标
- 要求速度尽量小还要达标
- 1不达标....2达标（所以答案是2）
- 速度最小就是1，而速度的最大值就是数组最大值因为就算定的越大（比数组最大值还大）都是1h内吃完，时间并没有任何变化
- 所以可以得到题目的答案（最小还达标）是在这个区间的
- 这个区间是单调性的：
- 速度变大花费的时间是越小的，比如说速度为6那么花费的时间是a小时，速度为7花费的时间是b小时，那么a >= b 的，也就是在最大中找最小
- 这道题就是速度越大越有可能达标，速度越小越不可能达标（比如说速度4是达标的，那么意味着速度5，6，7，8都是达标的），满足答案是单调的，所以能够通过对答案进行二分得到最终答案
- 对答案二分过程：
- 比如：1，2，3，4，5，6，7，8
- 第一次二分，检查4是否达标
- 如果4达标，及一个答案ans = 4,然后再1~3这个范围取一个更小的检查是否答案，因为题目要求的是最小还达标，如果2不达标，那么不计入答案,ans还是4，去3~3范围二分检查。
- 如果4不达标，那么意味着1~3都不达标，ans不记录答案去右侧二分，然后在5~8区间二分，6还不达标那么再在右侧二分，也就是7，8，发现7达标，记录答案ans = 7，那么在7的左侧二分，发现7的左侧已经没了，那么答案就是7了
- 那么我们需要一个check函数检查是否达标：
- 也就是检查用给的中间值的速度吃这堆香蕉花的时间。
具体代码讲解：
bool check(int* piles, int pilesSize, int h, int mid) {
long int sum = 0;
for (int i = 0; i < pilesSize; i++) {
if (piles[i] % mid != 0) {
sum += (piles[i] / mid) + 1;
}
else{
sum+=piles[i]/mid;
}
}
return sum <= h;
}
int minEatingSpeed(int* piles, int pilesSize, int h) {
// 最小且达标的速度，范围[l,r]
int l = 1;
int r = 0;
for (int i = 0; i < pilesSize; i++) {
if (piles[i] >= r)
r = piles[i];
}
//[l,r]不停的二分
int ans = 0;
while (l <= r) { // 直到二分范围消失
int mid = (r + l) / 2;
if (check(piles, pilesSize, h, mid)) {
// 达标，记录答案
// 左侧二分
ans = mid;
r = mid - 1;
} else {
// 不达标，不记答案
// 右侧二分
l = mid + 1;
}
}
return ans;
}410. 分割数组的最大值
题目
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], k = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], k = 2 输出：9
示例 3：
输入：nums = [1,4,4], k = 3 输出：4
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)
思路：
估计最终答案可能的范围
- 每部分累加和求出来的最大值尽量小（答案）
- 整个数组的和为A
- [0,A]
- 范围定得比较粗糙，可以定得特别粗糙，毕竟二分时间复杂度很低
分析问题的答案和给定条件之间的单调性
- 比如范围0~1000，对0~1000进行二分->500，相当于k份都要满足累加和<=500，
- 假如二分得600，也就是每一部分的累加和都<=600，那么条件放宽了，越有可能达标，
- 也就是答案越大越有可能，越小越不可能
建议一个check函数，当答案固定的情况下，判断给定的条件是否达标
- 根据题目建立check函数，在这道题当中check:
- 我们必须让数组每一份累加和满足<=mid，得到数组当中划分几部分可以满足这个要求，然后判断部分综合是否超过题目要求，超过了就是不达标没超过就是达标
- 比如[4,5,1,6,8,5,9]假如这时中间值是11，那么4+5+1小于11，如果加上6那么就多了，就开始装下一个part，起点从6开始。
- 但如果数组中有一个元素直接大于了给的中间值比如[3,3,77]假如给的中间值是15，77直接大于了15，那么我们要直接返回没有方案（即false）
在最终答案可能的范围上不断二分搜索，每次使用check函数判断，直到二分结束，找到最合适的答案
bool check(int* nums, int numsSize, int k, int mid) {
// 必须让数组每一份的累加和满足<=mid,请问划分成几个部分才够
// 一直加加到要超了，就停，代表一个子达成，
// 但如果单点的值就超过，直接用整数最大值表示没有方案
int parts = 1;
int sum = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > mid) {
return false;
}
if (sum + nums[i] > mid) {
parts++;
sum = nums[i];
} else {
sum += nums[i];
}
}
return parts <= k;
}
int splitArray(int* nums, int numsSize, int k) {
long int sum = 0;
for (int i = 0; i < numsSize; i++) {
sum += nums[i];
}
long int ans = 0;
long int l = 0;
long int r = sum;
//[0,ans]二分
while (l <= r) {
// 必须让数组每一份的累加和满足<=mid,请问划分成几个部分才够
int mid = (l + r) / 2;
if (check(nums, numsSize, k, mid)) {
// 如果你需要的部分数量<=给你的部分的数量说明达标
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}总结
- 估计最终答案可能的范围
- 分析问题的答案和给定条件之间的单调性
- 建议一个check函数，当答案固定的情况下，判断给定的条件是否达标
- 在最终答案可能的范围上不断二分搜索，每次使用check函数判断，直到二分结束，找到最合适的答案
- 核心：分析单调性，建立check函数