基本概念
将最值问题转换为判定
与二分查找的区别
二分查找:在一个已知的有序数据集上进行二分地查找
二分答案:答案有一个区间,在这个区间中二分,直到找到最优答案
如何判断一个题是不是用二分答案做的
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 <= 104
piles.length <= h <= 109
1 <= 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 <= 1000
0 <= nums[i] <= 106
1 <= 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函数