文章目錄
-
- 二分模闆
-
- 模闆1
- 模闆2
- 模闆3
- 使用二分的時機
- 二分下标系列
-
- 搜尋插入位置
-
- 二分
- 在排序數組中查找元素的第一個和最後一個位置
-
- （二分）
- 尋找旋轉排序數組中的最小值
-
- （二分）
- 尋找旋轉排序數組中的最小值Ⅱ
-
- （二分）
- 搜尋旋轉排序數組
-
- （樸素二分）
- （粗糙二分）
- 搜尋旋轉排序數組 ll
-
- （二分）
- （粗糙二分）
- 第一個錯誤版本
-
- （二分）
- （二分）
- 山脈數組的峰頂索引
-
- （暴力）
- （二分）
- （二分）
- （三分）
- 山脈數組中查找目标值
-
- （二分）
- （三分找峰值+二分找target）
- 二分答案系列
-
- x的平方根
-
- （二分）
- 數的三次方根
-
- （浮點數二分）
- 尋找重複數
-
- （暴力）
- （哈希映射）
- （排序）
- （二分）
- （雙指針）
- 轉變數組中最接近目标的數組和
-
- (二分1)
- （二分2）
- 判斷條件複雜的二分系列
-
- 愛吃香蕉的珂珂
-
- （二分）
- 分割數組的最大值（經典模闆題：最大值最小化）
-
- （動規）
- （二分+貪心）
- 在D天内送達包裹的能力
-
- （暴力）
- （二分+貪心）
- 制作m束花所需要的天數
-
- （二分）
- 小張的刷題計劃
-
- （二分 + 貪心）
- 總結：最大值最小化
▄█▔▉●
二分模闆
模闆1
int BinarySearch1(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {//
int mid = l + (r - l) / 2;
if (nums[mid] == target) {//
return mid;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
模闆2
int BinarySearch2(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {//
int mid = l + (r - l) / 2;
if (nums[mid] >= target) r = mid;//
else l = mid + 1;
}
if (nums[l] == target) return l;
else return -1;
}
int BinarySearch2(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
if (nums[l] == target) return l;
else return -1;
}
模闆3
int BinarySearch3(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target){
r = mid;
} else {
l = mid;
}
}
if (nums[l] == target) return l;
if (nums[r] == target) return r;
return -1;
}
使用二分的時機
當需要在一個範圍内，尋找一個數，并且這個數滿足可以将整個數組不重不漏地劃分為兩段的性質，就可以使用二分。
關鍵點：
1.題目的答案需要求出的是一個數字
2.需要在一個整體有序或者局部有序的範圍内尋找該數字
3.有一個題目的要求劃分的依據具有二段性
總結：說白了二分查找隻不過是因為數組自身滿足有序的這個特殊的性質，是以比順序查找效率高一點，是以在思考二分的時候，可以先想一想暴力求解是不是可以解出來，然後利用二分提高效率。
二分下标系列
搜尋插入位置
二分
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// 因為排除法最後的結果在[0, nums.size()-1]這個範圍内
// 是以如果target要插入在數組的最後就需要特判一下
if (target > nums.back()) return nums.size();
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
在排序數組中查找元素的第一個和最後一個位置
（二分）
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return {-1, -1};
// 二分相同元素的第一個位置
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] != target) return {-1, -1};
int first = l;
// 二分相同元素的最後一個位置
l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r + 1>> 1;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
int second = l;
return {first, second};
}
};
尋找旋轉排序數組中的最小值
（二分）
class Solution {
public:
int findMin(vector<int>& nums) {
if (nums.back() > nums.front()) return nums[0];
// 二分出第一個小于nums[0]的數字
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] > nums.back()) l = mid + 1;
else r = mid;
}
return nums[l];
}
};
尋找旋轉排序數組中的最小值Ⅱ
（二分）
class Solution {
public:
int findMin(vector<int>& nums) {
while (nums[0] == nums.back() && nums.size() > 1) nums.pop_back();
if (nums.back() > nums[0]) return nums[0];
int target = nums[0];// 如果選取nums[0]當做目标的話，就需要特判整個數組是否有序
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < target) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
搜尋旋轉排序數組
（樸素二分）
問題：一個無序的數組怎麼可以使用二分來求解呢？
一個完全無序的數組是不可以使用二分這樣的技巧來求解的，但是本題的無序是在旋轉一個有序數組之後才變得無序的，是以這樣的無序數組還是在局部上相對有序的。是以可以抓住旋轉的轉折點，這樣無序的數組就被分成兩個有序的小數組了，這樣就可以使用二分了。
問題：怎麼找轉折點？
抓住轉折點的特點，如果在旋轉之後，數組不是原數組的話，在轉折點的左右應該分别是最大值和最小值，而在一個旋轉數組中找最小值是可以求出來的，是以這樣就找到了轉折點。
解題方法：在一個數組中找到一個轉折點，然後分别在兩個局部有序的數組中找target。
class Solution {
public:
// 由于二分最小值需要找<=target的第一個值
// 而二分答案需要找>=target的第一個值，是以需要寫兩個二分
int BinarySearch(vector<int>& nums, int target, int start, int end) {
int l = start, r = end;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] == target) return l;
else return -1;
}
int search(vector<int>& nums, int target) {
// 找到最最小值的下标，這同時也就是兩端有序數組的分界點
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
// 在兩端有序數組上分别二分，然後找出答案
int pos = l;
int leftAns = BinarySearch(nums, target, 0, pos - 1);
int RightAns = BinarySearch(nums, target, pos, nums.size() - 1);
return leftAns == -1 ? RightAns == -1 ? -1 : RightAns : leftAns;
}
};
（粗糙二分）
第二種方法就像第一種方法那麼細緻地找到一個轉折點，然後才開始二分，這種方法就比較粗糙，但是也比較快一點。
第一種方法是求出了轉折點，然後二分。其實并沒有必要求出轉折點，因為數組最多隻有兩段，是以随便一個數組，一定會落在一段有序的數組上。
解題方法：首先
nums[mid]
跟
nums[l]
和
nums[r]
比較，找到出
nums[mid]
在一段有序的數組上。然後再和
target
比較，将
r
或者
l
定範圍。
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] == target) return mid;
// 數組的前半部分有序
if (nums[mid] >= nums[l]) {
// target在[l, mid)中
if (nums[mid] > target && target >= nums[l]) r = mid - 1;
else l = mid + 1;
}
// 數組的後半部分有序
if (nums[mid] <= nums[r]) {
// target在(mid, r]中
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
};
搜尋旋轉排序數組 ll
本題和上一道題目搜尋旋轉數組ll有什麼差別呢？
差別在于本題中，數組是一個數是按非降序排列的數組，數組中的數值可能會有相同的數字。這就破壞了二分的二段性。
什麼叫二段性呢？就是原來可以通過劃分數組，使得前半段中的數都
>nums.back()
，後半段中的數都
<= nums.back()
，這樣就可以找到旋轉數組的轉折點，然後将數組劃分成為兩個有序數組，最後對兩段有序數組分别進行二分找
target
。
但是不巧的是，現在如果有了相同的數字出現在數組中，那麼可能在找旋轉數組中的轉折點，前半段數組中的數也
>=nums.back()
，後半段數組中的數也
<=nums.back()
，如果不能将數組劃分成兩段數組的話，就不能使用二分來找到旋轉數組的轉折點了。
是以隻要把數組中的開頭和結尾相同的數字删除掉一端，不就又可以将前後兩段數組區分開來了麼。是以
while(nums.size() > 1 && nums.back() == nums[0]) nums.pop_back()；
把後面如果相同的數字删掉就可以了。
下面兩個版本都是在搜尋旋轉數組l的基礎上加上
while(nums.size() > 1 && nums.back() == nums[0]) nums.pop_back()；
就可了。
（二分）
class Solution {
public:
bool BinarySearch(vector<int>& nums, int l, int r, int target) {
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return nums[l] == target;
}
bool search(vector<int>& nums, int target) {
while (nums.size() > 1 && nums.back() == nums[0]) nums.pop_back();
// 找到<=nums.back()的第一個數
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
int pos = l;
// 在兩段有序數組中的尋找是否存在target
bool flag1 = BinarySearch(nums, 0, pos - 1, target) ;
bool flag2 = BinarySearch(nums, pos, nums.size() - 1, target);
return flag1 || flag2;
}
};
（粗糙二分）
class Solution {
public:
int search(vector<int>& nums, int target) {
while (nums.size() > 1 && nums.back() == nums[0]) nums.pop_back();
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] == target) return true;
// 這裡是>=,因為前半段數組中隻有一個數字了。如果不加上=的話，可能會錯過答案
// 數組的前半部分有序
if (nums[mid] >= nums[l]) {
// target在[l, mid)中
if (nums[mid] > target && target >= nums[l]) r = mid - 1;
else l = mid + 1;
} else {// 數組的後半部分有序
// target在(mid, r]中
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return false;
}
};
第一個錯誤版本
本題中顯然可以将數組中的數分成兩段，前面一段全是真，後面一段全是假，是以由二段性就可以想到使用二分。
有兩種版本的二分，第一種是找第一個false，第二種是找最後一個true然後+1。
（二分）
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (isBadVersion(mid)) r = mid;// 如果正确就向前縮小範圍
else l = mid + 1;
}
return l;
}
};
（二分）
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if(!isBadVersion(mid)) l = mid;
else r = mid - 1;
}
// 防止n=1,bad=1這種特殊的情況，沒有進入循環。是以還需要特判一步
return !isBadVersion(r) ? r + 1 : r;
}
};
山脈數組的峰頂索引
（暴力）
第一種方法是暴力，從前往後周遊，當
nums[mid] < nums[mid + 1]
繼續，當
nums[mid] > nums[mid + 1]
就停下來。
（二分）
既然是要在數組中找一個數，并且數組被分成了兩段，就要考慮是否可以使用二分，在使用二分之前需要考慮數組中的數是否具有【二段性】。
因為前面很多的二分的題目都是有一個
target
或者可以參考的數字，然後以這個數字為基準，然後将數組分成兩段。
但是這道題目好像沒有一個現成的參考數字給我們，但是不要局限在必須要找一個固定參考數字的思維中，因為二段性隻是要求有一個性質可以正好将數組分成兩段而已。經過仔細的觀察過後，不難發現前半段數組都是遞增的，而後半段數組都是遞減的，這不就将數組劃分成為兩段了麼。
是以根據這點可以有兩種二分，第一種是找第一個開始下降的數字的索引。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& nums) {
int l = 0, r = nums.size() - 2;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return l;
}
};
（二分）
第二種是找最後一個遞增的數字的索引。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& nums) {
// 因為nums.size()>=3，是以不用擔心不進入while的情況
int l = 0, r = nums.size() - 2;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] < nums[mid + 1]) l = mid;
else r = mid - 1;
}
return l + 1;
}
};
（三分）
還有一種方法：三分。一般三分問題可以解決單峰值問題。
三分：将數組分成三段，然後每一次通過派出1/3區間的方法，最後逼近到峰值。
具體做法：将區間分成
[L, mid1]
，
[mid1, mid2]
，
[mid2, R]
。如果
arr[mid1] > nums[mid2]
的話，說明峰值一定不在
[mid2, R]
區間内，是以
R = mid2 - 1
，同理如果
arr[mid2] > arr[mid1]
，峰值一定不在
[L, mid1]
中間，
L = mid1 + 1
。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (arr[mid1] > arr[mid2]) {
r = mid2 - 1;
} else {
l = mid1 + 1;
}
}
return l;
}
};
山脈數組中查找目标值
（二分）
本題看起來好像很難，但是其實就是三道題目的組合形式而已。
山脈數組中查找目标值=找峰值索引+在正序數組中找target+在逆序數組中找target
在 山脈數組的峰頂索引 中具體講解了如何利用二分或者三分尋找峰值的索引，而在正序數組或者逆序數組中找
target
就是二分的基本題型了。
/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
*/
class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int l = 0, r = mountainArr.length() - 2;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) > mountainArr.get(mid + 1)) r = mid;
else l = mid + 1;
}
int MaxIndex = l;// 峰值的索引
// 在數組的[0, MaxIndex]中尋找target
l = 0, r = MaxIndex;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) >= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
// 如果前半段數組中找不到target
// 就在[MaxIndex+1, mountainArr.length()-1]中尋找target
l = MaxIndex + 1, r = mountainArr.length() - 1;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) <= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
else return -1;
}
};
（三分找峰值+二分找target）
/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
*/
class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
// 三分尋找峰值的索引
int l = 0, r = mountainArr.length() - 1;
while (l < r) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (mountainArr.get(mid1) > mountainArr.get(mid2)) {
r = mid2 - 1;
} else {
l = mid1 + 1;
}
}
int MaxIndex = l;// 峰值的索引
// 在數組的[0, MaxIndex]中尋找target
l = 0, r = MaxIndex;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) >= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
// 如果前半段數組中找不到target
// 就在[MaxIndex+1, mountainArr.length()-1]中尋找target
l = MaxIndex + 1, r = mountainArr.length() - 1;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) <= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
else return -1;
}
};
二分答案系列
x的平方根
（二分）
一個數x的平方根一定在
[0, x]
之間，一看到在一個有序的範圍内尋找一個數值就可以聯想到二分。但是是否可以使用二分找出一個目标值，還需要判斷尋找這個數值的邏輯是否可以将整個範圍内的數分成兩段。即是否具有二段性。
不難發現，這段範圍的數中，所有數的平方要麼
>x
，要麼
<x
，要麼
==x
。是以這就可以不重不漏的将所有的數都考慮到了，是以就可以使用二分。雖然前面這句話看起開很像廢話，但是下次遇到更難的題目的時候，也可以用這個思路去判斷是否可以用二分解題。
class Solution {
public:
int mySqrt(int x) {
if (x == 0 || x == 1) return x;// 如果是0或者1，就直接傳回x
uint64_t l = 0, r = x / 2;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (mid <= x / mid) l = mid;
else r = mid - 1;
}
return l;
}
};
數的三次方根
（浮點數二分）
上面一道題目是整數二分，這道題目是一個浮點數二分，就是在一個範圍内尋找一個浮點數。
其實邏輯和整數二分是差不多的。但是要注意的是：因為浮點數的比價不能像整數比較那樣，十分明确用
==
來比較兩個數的相等性。
因為浮點數的存儲的緣故，是以在精度0兩個數上永遠不可能相等。是以規定在兩個數小于某一個很小的數（如
1e-6
）的時候，就判定兩個數相等了。
浮點數二分不僅在比較兩個數的時候比較特殊，在劃定範圍的時候也比較特殊。在整數二分的時候因為除法的向下取整和可能數組中有多個相同的數，是以需要控制二分的邊界。但是二分浮點數的時候就不用考慮這麼多，直接判斷，然後要麼
l = mid
，要麼
r = mid
。因為浮點數在數字中隻有一個并且浮點數的除法也沒有向下取整的說法。
總結：在浮點數二分的時候，第一需要在兩個數比較的時候，拿一個很小的數作參考。第二在縮小範圍的時候，不用考慮邊界。
#include <iostream>
using namespace std;
#define eps 1e-6
int main()
{
double x;
cin >> x;
double l = -1000, r = 1000;
while ((r - l) >= eps) {
double mid = (r + l) / 2.0;
if (mid * mid * mid <= x) l = mid;
else r = mid;
}
printf("%.6f\n", l);
return 0;
}
尋找重複數
（暴力）
暴力就是将所有的數全部兩兩比較，中間發現有重複的數字就直接傳回該數字。
暴力的方法并沒有用到數組中的數全部都在
[1, n]
之間這個特點，是以使用性最強但是也是最慢的。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
for (int i = 0; i < nums.size(); i ++) {
int num = nums[i];
for (int j = i + 1; j < nums.size(); j ++) {
if (num == nums[j]) return num;
}
}
return 0;
}
};
- 時間複雜度O(N2)
- 空間複雜度O(1)
（哈希映射）
因為數組中n+1個數，全部都在
[1, n]
之間，是以本應該是一個蘿蔔一個坑，但是現在有一個坑位有兩個蘿蔔，先要找出那個多出的蘿蔔。
這樣不難想到可以使用哈希表，将每一個數字都映射到數組中的一個位置上。順着這個思路，可以周遊這個數組，然後将數字映射到數組中相應的位置上，如果返現該位置上已經有數字了，就傳回該重複數字。（也可以使用
unordered_set
哈希表）。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
vector<int> cnt(n + 1, 0);
// 将nums[i]放在第nums[i]個位置上
// 如果一個位置被放了兩次，就說明該數字為重複數字
for (int i = 0; i < nums.size(); i ++) {
if (cnt[nums[i]] != 0) return nums[i];
cnt[nums[i]] = nums[i];
}
return 0;
}
};
- 時間複雜度O(N)
- 空間複雜度O(N)
（排序）
既然是重複的數字，那麼排序之後兩個重複的數字一定會緊挨在一起。是以隻要排完序之後，找出相鄰且相等的元素就是重複的元素。
利用排序算法也沒有用到數組中的數都在
[1, n]
之間的特性。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1; i ++) {
if (nums[i + 1] == nums[i]) return nums[i];
}
return 0;
}
};
- 時間複雜度O(Nlogn)
- 空間複雜度O(1)
（二分）
根據抽屜原理：在10個抽屜中放11個蘋果，那麼至少有一個抽屜中有2個蘋果。
在
[1, n]
的範圍中有一個數m，如果在數組
nums
中
<=m
的個數
==m
的話之前的數字，說明是m不是重複的元素。但是如果在數組
nums
中
<=m
的個數
>m
的話，就說明m是重複的元素之後的數字或者m就是重複數字，因為原本
個數==m
但是由于m是重複的元素，是以小于等m的個數會多出一個。
像這樣通過個數可以将
[1,n]
分成兩段（重複數字之前
個數==m
，重負數字之後或者重複數字
個數>m
），就可以使用二分。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1, r = nums.size() - 1;// 搜尋區間為[1, n(即nums.size() - 1)]
while (l < r) {
int mid = l + r >> 1;
// 統計<= mid的個數
int cnt = 0;
for (int num : nums) {
if (num <= mid) cnt ++;
}
// 縮小範圍
if (cnt > mid) r = mid;
else l = mid + 1;
}
return l;
}
};
- 時間複雜度O(Nlogn)
- 空間複雜度O(1)
（雙指針）
因為數組中的數字都是在
[1,n]
之間的，是以如果沒有重複的數字的話，如果按照
m = nums[m]
這樣的邏輯的話，一定會形成一條連結清單，如
nums={1, 2, 3, 4}
，形成
1->2->3->4
。（這一點很難聯想到，可以這麼想：因為沒有相同數字并且沒有數字0（從1開始[1,n]範圍内），是以兩個數字之間不可能互相指向）。
如果數組中有重複的數字，那麼兩個數字之間就有可能互相指向，這樣就形成了一個閉環的連結清單，而重複數字就是連結清單的入環口。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int fast = 0, slow = 0;
while (1) {
fast = nums[nums[fast]];
slow = nums[slow];
if (slow == fast) break;
}
fast = 0;// 從頭開始走
while (slow != fast) {
fast = nums[fast];
slow = nums[slow];
}
return fast;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
轉變數組中最接近目标的數組和
(二分1)
其實本題就是在
[0, max(arr[i])]（max(arr[i])是指arr數組中的最大值）
中尋找一個數
mid
，該數字可以是的數組中的所有
>mid
的數字都變成
mid
，最後可以 使得數組中的和最接近
target
。
本題的難點在于需要找到最接近
target
的數字，而不是找到具體的某一個整數。
如果這題改成找到數組和等于
target
(保證一定有解)，這樣你會不會？這就改過之後就變成了一個經典的二分問題了。這就可以直接使用二分，然後在再
check()
函數中判斷第一個使得數組和
>=target
的數字。傳回即可。
其實寫到這裡就已經很接近答案了，為什麼？因為最接近
target
的數字一定是兩個，一個數可以使得數組和
>=target
，一個數可以使得數組和
<=target
。是以如果求出了第一個可以使得數組和
>=target
的數字
left
，那麼另一個可以使得數組和最接近
target
的數字就是
left - 1
了。最後比較一下
left
和
left-1
拿一個可以使得數組和更接近
target
就可以了。
class Solution {
public:
int Sum(int mid, vector<int>& arr) {
int sum = 0;
for (int num : arr) sum += min(num, mid);
return sum;
}
int findBestValue(vector<int>& arr, int target) {
int l = 0, r = 0;
for (int n : arr) r = max(r, n);
while (l < r) {
int mid = l + r >> 1;
if (Sum(mid, arr) >= target) r = mid;
else l = mid + 1;
}
int up = Sum(l, arr);
int low = Sum(l - 1, arr);
if (abs(up - target) < abs(target - low)) return l;
else return l - 1;
}
};
（二分2）
當然出來求出第一個使得數組和
>=target
的數。也可以求出最後一個
<=target
的數字
right
，然後比較
right
和
right + 1
哪一個可以使得數組和更接近
target
。
class Solution {
public:
int Sum(int mid, vector<int>& arr) {
int sum = 0;
for (int i = 0; i < arr.size(); i ++) sum += min(arr[i], mid);
return sum;
}
int findBestValue(vector<int>& arr, int target) {
int l = 0, r = 0;
// // 尋找最大值r
for (int n : arr) r = max(r, n);
while (l < r) {
int mid = l + r + 1 >> 1;
if (Sum(mid, arr) <= target) l = mid;
else r = mid - 1;
}
int low = Sum(l, arr);
int up = Sum(l + 1, arr);
if (abs(low - target) <= abs(target - up)) return l;
else return l + 1;
}
};
判斷條件複雜的二分系列
愛吃香蕉的珂珂
（二分）
這道題翻譯一下就是在一個範圍内尋找一個數，該數字使得将所有數抵消掉的次數
<=H
，求出該數字的最小值。
這就很像二分的題目，求出一個數字滿足某一個性質。
是以套入二分的模闆，發現就是求出時間
<=h
的第一個數。注意本題再求出h的時候有一點繞，因為當
mid
越小的時候花費的時間越長，
mid
越大的時候，花費的時間月小。是以當算出的時間
<=h
的時候，
r = mid
應該縮小右邊的範圍。
除法的向上取整小技巧：(a + b - 1) / b
class Solution {
public:
int Hour(int mid, vector<int>& piles) {
int cnt = 0;
for (int n : piles) {
cnt += (n + mid - 1) / mid;// n/mid向上取整
}
return cnt;
}
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1, r = 0;// l從1開始，因為除法中除數不能為0
// 範圍[1, max(piles[i])]
for (int n : piles) r = max(n, r);
while (l < r) {
int mid = l + r >> 1;
// 找到第一個<=h的數字
// mid越小，時間越大
if (Hour(mid, piles) <= h) r = mid;
else l = mid + 1;
}
return l;
}
};
分割數組的最大值（經典模闆題：最大值最小化）
其中非負整數和連續的子數組很重要
（動規）
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
vector<vector<int>> dp(nums.size() + 1, vector<int>(m + 1, INT_MAX));
// 求出字首和
vector<int> sum(nums.size() + 1, 0);
for (int i = 1; i <= nums.size(); i ++) sum[i] = nums[i - 1] + sum[i - 1];
dp[0][0] = 0;
for (int i = 1; i <= nums.size(); i ++) {// 數組長度
for (int j = 1; j <= m; j ++) {// 分割後子集的個數
for (int k = 0; k < i; k ++) {
dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[i] - sum[k]));
}
}
}
return dp[nums.size()][m];
}
};
（二分+貪心）
class Solution {
public:
// 求出數組中最大和不超過maxSum的情況下，nums要被分成幾段
int split(vector<int>& nums, int maxSum) {
int subCnt = 1;// 數組中連續集合的個數
int curSum = 0;
for (int num : nums) {
if (curSum + num > maxSum) {
subCnt ++;
curSum = 0;
}
curSum += num;
}
return subCnt;
}
int splitArray(vector<int>& nums, int m) {
int l = 0, r = 0;// l是一個數中的最大值，r是整個數組中的最大值即整個數組的和
int sum = 0;
for (int num : nums) {
l = max(num, l);
sum += num;
}
r = sum;
while (l < r) {
int mid = l + r >> 1;
if (split(nums, mid) <= m) r = mid;
else l = mid + 1;
}
return l;
}
};
在D天内送達包裹的能力
（暴力）
首先可以來想一下暴力方法怎麼解？
要求的是在D天内需要送達包裹，需要的最低載重能力。重點在這個最低載重能力上，現在不妨先預估一下載下傳重能力可以去哪些數，如果一天可以載重是無限大，那麼無論是多少件物品都可以1天内送達，這個是最大的例子，如果比無限大小一點呢？還是1天内送到。我們發現需要滿足D天内的送達的數值原來可以有很多，那麼我們就來往小的預估。如果不考慮天數，需要将所有貨物送到需要的最低載重能力是多少，不難發現就是所有貨物中載重最重的那一個貨物，因為如果要将所有的貨物送到，每一個貨物不可能劈成兩半送往，是以要保證将最重的貨物送達就需要最低的載重能力為最重貨物的重量。
經過上面一分析，最低的載重能力其實就在
[max(weight[i]), 無限大]
，但是這個無限大也可以縮小一點吧。如果所有貨物要1天送到，載重能力就是所有貨物的重量總和。是以載重能力就是
[max(weights[i]), sum(weights[i])]
因為送貨物的順序必須按照順序送，也就是數組中的數必須要連續的取用，是以如果給了一個載重能力，就可以算出對應的送貨天數。
綜上：已經有了總重能力的範圍，也可以根據送貨的總重算出對應的天數，如此就可以暴力的将所有載重能力算出對應的天數，然後和預期的
days
比較。如果載重能力是正向枚舉的，那麼第一個滿足送貨天數
<=days
的載貨能力就是最低的載貨能力。（days和載貨能力成反比，載貨能力越強，days越小）
class Solution {
public:
int split(vector<int>& weights, int maxLoad) {
int days = 1;// 送貨至少要一天
int curLoad = 0;// 目前的貨物載重量
for (int w : weights) {
if (curLoad + w > maxLoad) {// 如果目前數加上之後>maxLoad的話，就說明載重達到上限
days ++;
curLoad = 0;
}
curLoad += w;
}
return days;
}
int shipWithinDays(vector<int>& weights, int days) {
int l = 0, r = 0;
for (int w : weights) {
l = max(l, w);
r += w;
}
for (int i = l; i <= r; i ++) {
if (split(weights, i) <= days) return i;
}
return 0;
}
};
（二分+貪心）
經過暴力方法的分析，可以提煉出從一個範圍的數中，尋找出一個數，該數字滿足使得送貨的天數
<=days
。
是以就可以不用順序查找了，可以使用二分開解決該問題。
class Solution {
public:
int split(vector<int>& weights, int maxLoad) {
int days = 1;// 送貨至少要一天
int curLoad = 0;// 目前的貨物載重量
for (int w : weights) {
if (curLoad + w > maxLoad) {// 如果目前數加上之後>maxLoad的話，就說明載重達到上限
curLoad = 0;
days ++;
}
curLoad += w;
}
return days;
}
int shipWithinDays(vector<int>& weights, int days) {
int l = 0, r = 0;
for (int w : weights) {
l = max(l, w);
r += w;
}
while (l < r) {
int mid = l + r >> 1;
if (split(weights, mid) <= days) r = mid;
else l = mid + 1;
}
return l;
}
};
制作m束花所需要的天數
（二分）
求的是摘m束花最少需要等待幾天。
可以知道如果在
m * k <= bloomDay
的情況下，隻要等待所有的花開就一定可以摘m束花。是以等待的天數就可以确定下來，一定在
[0, max(bloomDay[i])]
中間。
是以隻要在這個範圍内，計算出一個數可以使得連續的k朵花成為一束，然後得到m束花即可。并且這個數要求是一個可以滿足得到花束
>=m
的一個數。這就可以使用二分了。
class Solution {
public:
int calcFlowers(vector<int>& bloomDay, int maxDays, int k) {
int cnt = 0;// 花束的個數
int flowers = 0;// 目前花的朵數
for (int day : bloomDay) {
if (day <= maxDays) {
flowers ++;
} else {
flowers = 0;
}
if (flowers == k) {
cnt ++;
flowers = 0;
}
}
return cnt;
}
int minDays(vector<int>& bloomDay, int m, int k) {
if (m * k > bloomDay.size()) return -1;
int l = 1e9, r = 0;// 已經過的天數
for (int d : bloomDay) {
l = min(l, d);
r = max(r, d);
}
while (l < r) {
int mid = l + (r - l) / 2;
if (calcFlowers(bloomDay, mid, k) >= m) r = mid;
else l = mid + 1;
}
return l;
}
};
小張的刷題計劃
（二分 + 貪心）
class Solution {
public:
int CalcDays(vector<int>& time, int mid) {
int cnt = 1;
int curSum = 0;// 目前刷題累計的耗時
int maxVal = 0;// 記錄耗時最多的題目
for (int t : time) {
curSum += t;
maxVal = max(maxVal, t);
if (curSum - maxVal > mid) {
cnt ++;
maxVal = t;
curSum = t;
}
}
return cnt;
}
int minTime(vector<int>& time, int m) {
int l = 0, r = 0;
for (int t : time) {
r += t;
}
while (l < r) {
int mid = l + r >> 1;
if (CalcDays(time, mid) <= m) r = mid;
else l = mid + 1;
}
return l;
}
};
總結：最大值最小化
适合的題目：1.連續的子數組的和 2.數組是非負整數