【算法深練】二分答案：從「猜答案」到「精準求解」的解題思路

前言

二分求最小值

1283. 使結果不超過閾值的最小除數

2187. 完成旅途的最少時間

1011. 在 D 天內送達包裹的能力

875. 愛吃香蕉的珂珂

3296. 移山所需的最少秒數

475. 供暖器

2594. 修車的最少時間

1482. 制作 m 束花所需的最少天數

3048. 標記所有下標的最早秒數 I

求最小值拓展（浮點型）?

1870. 準時到達的列車最小時速

3453. 分割正方形 I

二分求最大值

275. H 指數 II

2226. 每個小孩最多能分到多少糖果

2982. 找出出現至少三次的最長特殊子字符串 II

2576. 求出最多標記下標

1898. 可移除字符的最大數目

1802. 有界數組中指定下標處的最大值

1642. 可以到達的最遠建筑

2861. 最大合金數

總結

前言

二分答案與二分查找【算法深練】二分查找：從O(n)到O(log n)以對數級效率秒殺海量數據的解題利刃-CSDN博客有異曲同工之妙，與二分查找不同的是：二分答案需要自己編寫check函數來判斷是否成立。二分答案在我們解題中是比較常用的，如果一個題目無從下手，可以先思考如果在已知答案的情況下，對答案進行判斷是否更簡單，如果更簡單就可以考慮使用二分來AC。

PS：本篇博客中的所有題目均來自于靈茶山艾府 - 力扣（LeetCode）分享的題單。?

二分求最小值

1283. 使結果不超過閾值的最小除數

題解：找到一個不大于threshold的整數，找到數組中除以該整數后仍然小于thorshold的最小除數。根據nums.length<=threshold如果除數是最大值結果就是nums.length滿足條件，所以區間就在(0,max(nums)]中對該區間中的所有數進行枚舉找到滿足條件的最小值，時間復雜度是O(N^2)太慢了。當除數變大的時候結果就在減小，那不就是單調的嗎，能使用二分來解決；將左右邊界分別設置為0和max(nums)，進行二分找到滿足條件的最小值。細節：向上取整a/b就是(a+b-1)/b向下取整。

class Solution {//計算如果除數是x結果時多少int div(vector<int>& nums,int x){int ret=0;for(auto e:nums) ret+=(e+x-1)/x;return ret;}
public:int smallestDivisor(vector<int>& nums, int threshold) {int n=nums.size();        //以數組小標表示除數，隨著下標增大結果也在減小所以可以使用二分int left=0,right=ranges::max(nums);   //使用左開右開的形式  n<=threshold所以最大值是除數為nums[n-1]時結果是nwhile(left+1<right){int mid=left+(right-left)/2;if(div(nums,mid)<=threshold) right=mid;  //滿足條件else left=mid;   //不滿足條件}return right;}
};

2187. 完成旅途的最少時間

題解：與類似，當時間在增大時旅途趟數也在增加是遞增的可以使用二分進行查找。左右邊界怎么進行設置呢？？？右邊界可以設置為min(time)*totalTrips表示最快的車獨自完成的時間，左邊界可以直接設置為0，也可以設置為min(time)。

class Solution {//時間time內完成的旅途數目long long numsTime(vector<int>& nums,long long time){long long ret=0;for(auto e:nums) ret+=time/e;return ret;}public:long long minimumTime(vector<int>& time, int totalTrips) {//以時間作為二分，時間越長可以完成的旅途越多是單調的//最長時間可以設置為：min(time)*totalTrips即花費最短時間的車輛獨自完成時間long long left=0,right=(long long)ranges::min(time)*totalTrips;while(left+1<right){long long mid=left+(right-left)/2;if(numsTime(time,mid)>=totalTrips) right=mid;else left=mid;}return right;}
};

1011. 在 D 天內送達包裹的能力

題解：當運輸能力上升時，所需要的時間就在減小所以滿足遞減，可以使用二分。在下邊界世界設置為0即可，上邊界設置為：全部包裹是max(weight)的情況下需要的載重能力，即max(weight)*((n-1)/days+1)，其中((n-1)/days+1)表示一天至多運輸貨物的數量；上邊界也可以使用所有貨物的總重量，表示一天就裝完所需的載重能力。

class Solution {//計算運載能力為x時需要的時間long long time(vector<int>& nums,long long x){long long tmp=0,ret=0;for(auto e:nums){if(e>x) return -1;tmp+=e;if(tmp>=x){ret++;tmp=tmp==x?0:e;}}if(tmp) ret++;return ret;}public:int shipWithinDays(vector<int>& weights, int days) {//船運載能力越強所需的時間就越短，是單調遞減的可以使用二分來解決int n=weights.size();//右邊界設置為如果貨物全是weight的最大值當時間為days時需要的運載能力//(n-1)/days+1表示包裹數量除以天數向上取整，即一天至多需要運輸多少個包裹long long left=0,right=ranges::max(weights)*((n-1)/days+1);while(left+1<right){long long mid=left+(right-left)/2;int need=time(weights,mid);if(need>0&&need<=days) right=mid;else left=mid;}return right;}
};

875. 愛吃香蕉的珂珂

題解：速度越快需要的時間就越小，單調遞減可以使用二分查找；下邊界可以使用0表示，上邊界使用piles的和表示。

class Solution {long long hours(vector<int>& nums,long long v){long long ret=0;for(auto e:nums)ret+=(e-1)/v+1;return ret;}public:int minEatingSpeed(vector<int>& piles, int h) {//速度越大，所需要的時間越短，單調遞減的可以使用二分解決//細節：她將吃掉這堆的所有香蕉，然后這一小時內不會再吃更多的香蕉。 說明需要進行向上取整int n=piles.size();//下邊界用0來表示，上邊界可以用所有的香蕉個數表示long long left=0,right=accumulate(piles.begin(),piles.end(),0LL);while(left+1<right){long long mid=left+(right-left)/2;if(hours(piles,mid)<=h) right=mid;else left=mid;}return right;}
};

3296. 移山所需的最少秒數

題解：當花費的時間越多時高度降低的就越多，所以可以使用二分來找最小值。下邊界可以使用0，上邊界可以用最快的工人一個人移山所需要的時間。

計算一個工人在t時間內可以降低的高度：

class Solution {//計算所有工人在t內降低的高度long long totalHeight(vector<int>& nums,long long t){long long ret=0;for(auto e:nums) ret+=height(e,t);return ret;}//計算工人在時間t內降低的高度long long height(int worktime,long long t){long long k=t/worktime;long long len=(-1+sqrt(1+8*k))/2;return len;}public:long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {//當時間越多降低的高度越長，可以使用二分解決long long left=0,right=0;long long heig=0,mintime=ranges::min(workerTimes),each=0;//確定上邊界rightwhile(heig<mountainHeight){each+=mintime;right+=each;heig++;}while(left+1<right){long long mid=left+(right-left)/2;if(totalHeight(workerTimes,mid)>=mountainHeight) right=mid;else left=mid;}return right;}
};

475. 供暖器

題解：當半徑越大時越滿足條件，房屋只存在能供暖和不能供暖兩種情況，所以可以使用二分進行查找；對于二分判斷是否滿足條件不需要考慮太多，直接將設置的x帶入題目進行檢驗即可。

class Solution {//檢查當前x時候滿足條件bool check(vector<int>& houses,vector<int>& heaters,int x){int n=houses.size(),m=heaters.size();int j=0;for(int i=0;i<n;i++){if(houses[i]>=heaters[j]-x&&houses[i]<=heaters[j]+x) continue;while(j<m&&houses[i]>heaters[j]+x) j++;if(j==m||houses[i]<heaters[j]-x) return false;}return true;}public:int findRadius(vector<int>& houses, vector<int>& heaters) {//先對兩個數組進行排序sort(houses.begin(),houses.end());sort(heaters.begin(),heaters.end());int left=-1,right=1000000000;  //設置上下邊界while(left+1<right){int mid=left+(right-left)/2;if(check(houses,heaters,mid)) right=mid;else left=mid;}return right;}
};

2594. 修車的最少時間

題解：與上一題類似，依舊是使用二分來解決。先確定上下邊界，下邊界直接設為0，上邊界可以使用最快修理工獨自完成所需要的時間。

class Solution {long long check(vector<int>& ranks,long long t){long long ret=0;  //統計修理好的車輛for(auto r:ranks) ret+=sqrt(t/r);  return ret;}public:long long repairCars(vector<int>& ranks, int cars) {//確定上下邊界long long left=0,right=0;long long r_min=ranges::min(ranks);right=r_min*cars*cars;while(left+1<right){long long mid=left+(right-left)/2;if(check(ranks,mid)>=cars) right=mid;else left=mid;}return right;}
};

1482. 制作 m 束花所需的最少天數

題解：二分+分組循環；對時間進行二分，下邊界使用0，上邊界可以使用bloomDay中的最大值；使用check來判斷時間t是否滿足條件。

class Solution {//檢查在t時刻是否滿足條件bool check(vector<int>& nums,int m,int k,int t){int i=0,n=nums.size();while(i<n){while(i<n&&nums[i]>t) i++;int start=i++;while(i-start!=k&&i<n&&nums[i]<=t) i++;if(i<=n&&i-start==k) m--;if(m==0) return true;}return false;}public:int minDays(vector<int>& bloomDay, int m, int k) {int n=bloomDay.size();if((long long)k*m>n) return -1;  //數量不夠直接返回int left=0,right=ranges::max(bloomDay);  //取上下邊界while(left+1<right){int mid=left+(right-left)/2;if(check(bloomDay,m,k,mid)) right=mid;else left=mid;}return right;}
};

3048. 標記所有下標的最早秒數 I

題解：此題難度較大，直接計算時間比較難，但是如果已知答案確定答案是否正確就比較簡單，就是二分。標記所有的下標，時間越多越有可能進行標記，所以可以根據時間進行二分。

題意轉換：此題可以理解為有n+1場考試[1,n]，我們需要對考試進行準備，每一場考試需要準備的時間是確定的，考試可以有多場；根據上面轉換后的題意，如果考試越靠后就有更多的時間進行準備，那就可以只準備每門考試的最后一場即可。

代碼細節：統計每門考試的最后一場時間，當時間到最后一場時必須進行考試，看前面可以準備的時間夠不夠即可。

class Solution {//檢查時間為t時，是否滿足條件bool check(vector<int>& nums,vector<int>& changeIndices,int t){int n=nums.size();vector<int> last_n(n,-1);for(int i=0;i<t;i++)last_n[changeIndices[i]-1]=i;  //存儲各個科目最后一次考試時間if(ranges::find(last_n,-1)!=last_n.end()) return false;   //存在沒有考試時間的科目int have=0;//i表示時間,changeIndices[i]-1是第幾門科目,nums[changeIndices[i]-1]是該門復習需要的時間for(int i=0;i<t;i++){if(i==last_n[changeIndices[i]-1]){if(have<nums[changeIndices[i]-1]) return false;else have-=nums[changeIndices[i]-1];}else have++;}return true;         }public:int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {int n=nums.size(),m=changeIndices.size();if(n>m) return -1;int left=n-1,right=m+1;  //不能確定時間為m時是否滿足條件，但是m+1是一定不滿足條件的所以將right置為m+1while(left+1<right){int mid=left+(right-left)/2;if(check(nums,changeIndices,mid)) right=mid;else left=mid;}return right>m?-1:right;}
};

求最小值拓展（浮點型）?

1870. 準時到達的列車最小時速

題解：依舊是二分，但是此題需要特別注意的是小數的處理方式，以及左右邊界的處理細節。細節：列車都是整點運行的，所以除了最后一輛列車其他的列車運行時間都要進行向上取整。

class Solution {//檢查是否滿足條件//因為車都是在整數時間發車的所以要進行向上取整bool check(vector<int>& dist,double hour,int v){int n=dist.size();double total=0;for(int i=0;i<n-1;i++)total+=(dist[i]-1)/v+1;total+=dist[n-1]/(double)v;return total<=hour;}public:int minSpeedOnTime(vector<int>& dist, double hour) {//當速度越大時多需要的時間也短，可以使用二分的方式來求最小速率int n=dist.size();if(n-1>=hour) return -1;  //車次-1時因為最后一次算的是小數而并不需要取整long long left=0,right=ranges::max(dist);  //right用dist中的最大值替代，這樣每輛車都只需要行駛一個小時double point=hour-(int)hour;            //如果最后一次出現小數時就需要對最后一次車速進行判斷，來確定right是否需要擴大if(point!=0&&dist[n-1]/point>right) right=dist[n-1]/point+1;while(left+1<right){int mid=left+(right-left)/2;if(check(dist,hour,mid)) right=mid;else left=mid;}return right;}
};

3453. 分割正方形 I

題解：易得y一定是存在的，所以此題的難點在于如何確定循環條件。此題以y作為二分基準，當下方面積更大（沒有找到準確位置）或者上下面積差在題目范圍內（找到了滿足條件的位置，但是可能不是最小y ）時將right=mid，否則將left=mid；

循環條件應該如何進行設置？？？

class Solution {//判斷以t為分界線是否滿足條件bool check(vector<vector<int>>& squares,double t){double down=0,up=0;for(auto& nums:squares){double x=nums[0],y=nums[1],len=nums[2];if(y+len>t)up+= len*min(y+len-t,len);  //注意此處不能直接將len*(y-len-t)其中間可能有空隙if(y<t)down+= len*min(t-y,len);}return up<down||abs(up-down)<=1e-5;  //當下面面積大時right就需要下移，當滿足條件時right也下移找最小值}public:double separateSquares(vector<vector<int>>& squares) {double left=0,right=0;for(auto nums: squares)if(nums[1]+nums[2]>right) right=nums[1]+nums[2];for(int i=0;i<48;i++)  //通過計算可以設置循環次數來對數據進行精確{double mid=left+(right-left)/2.0;if(check(squares,mid)) right=mid;else left=mid;}return right;}
};

上面通過計算直接確定了循環的次數，但是如果仍然像之前一樣寫也是可以的，

for(int i=0;i<48;i++)可以寫成while(left+1e-5<right)，此寫法仍然控制了區間長度不超過1e-5.

但是此處不建議用while本題能夠過是因為left和right的值較小，當left值很大的時候left+1e-5的結果可能不再是我們預期的結果，此處與浮點數的存儲有關，下面進行簡單解釋；

存儲浮點數的時候會先將浮點數轉換為(1.xxxxxxxxxx)*(10^m)的形式在64位下只有52個比特位來存儲小數點后面的數據，所以浮點數實際上是不連續的，也就是說1.0的下一個浮點數是1+2^(-52)，當這個數越大的時候其下一個浮點數也就越大，所以當left很大時left+1e-5還是left，就會進入死循環。

拓展：此題如果數據范圍較小的話，也可以將所有的整數都提升10^5來將浮點數二分轉化為整數二分。

二分求最大值

求最大值和求最小值的方法是類似的，只不過判斷條件不一樣。

275. H 指數 II

題解：數組是單調遞增的，當h越大的時候需要的優質論文的個數就越多；所以可以使用二分來找到滿足條件的h。假設論文被引用的次數>=h的個數是i，當i>=h時說明滿足條件但是不一定是最大的一個讓left=mid，當i<h時說明right太大了，所以將right進行縮小right-mid即可。

class Solution {//h表示論文被應用的次數bool check(vector<int>& nums,int h)  {int n=nums.size();int pos=ranges::lower_bound(nums,h)-nums.begin();//判斷是否有h個值滿足條件return n-pos>=h;}public:int hIndex(vector<int>& citations) {//數據是有序的，可以通過二分來進行查找int n=citations.size();int left=0,right=citations[n-1]+1;while(left+1<right){int mid=left+(right-left)/2;if(check(citations,mid)) left=mid;else right=mid;}return left;}
};

2226. 每個小孩最多能分到多少糖果

題解：當直接求答案比較難的時候，可以考慮用驗證法；在已知答案的情況下，對答案的正確性進行驗證，就是二分。使用二分先確定一個分到的糖果數，再檢驗該答案是否正確即可。

class Solution {//能否每人分到x個糖果bool check(vector<int>& nums,long long x,long long k){long long count=0;  //記錄能有多少人分到x個糖果for(auto e:nums) count+=e/x;return count>=k;}public:int maximumCandies(vector<int>& candies, long long k) {//直接進行求比較難，但是如果已知答案判斷答案是否正確就比較簡單了//已知答案就需要考慮二分long long left=0,right=ranges::max(candies)+1;while(left+1<right){long long mid=left+(right-left)/2;if(check(candies,mid,k)) left=mid;else right=mid;}return left;}
};

2982. 找出出現至少三次的最長特殊子字符串 II

當出現了相同子字符串時，第一時間想到的是滑動窗口。用滑動窗口求出每一個相同子串，每個相同字符串又可以進行分割出更多的子字符串，將這些字符串進行統計找出出現三次以上的最長子串。看起來好像可以！！！

class Solution {
public:int maximumLength(string s) {//使用一次滑動窗口unordered_map<string ,int> m;int n=s.size();int i=0;while(i<n){int start=i;while(i<n&&s[start]==s[i]) i++;//此時相同字符串的長度為i-startint len=i-start;string str(s.begin()+start,s.begin()+i);for(int k=len;k>=0;k--)m[str.substr(0,k)]+=len-k+1;  //進行統計}//所有相同的字符串都存儲到m中了，找長度最長的并且有3個int ret=-1;for(auto& [str,k]:m){if(k>=3) ret=max(ret,(int)str.size());}return ret;}
};

以上對思路進行實現，但是沒有過，是的。因為當相同字符串很長時就會導致map中存儲了大量字符串導致最后內存超出限制！！！。

所以需要對代碼進行優化，每次統計的時候都是直接把所有的子字符串都統計進去，能不能進行一點裁剪，可以。對for循環進行修改：for(int k=len;k>=len-2&&k>0;k--)只需要統計最長的三個即可，因為如果一個相同字符串長度為len則其滿足條件的長度至少為len-2。

class Solution {
public:int maximumLength(string s) {//使用一次滑動窗口unordered_map<string ,int> m;int n=s.size();int i=0;while(i<n){int start=i;while(i<n&&s[start]==s[i]) i++;//此時相同字符串的長度為i-startint len=i-start;string str(s.begin()+start,s.begin()+i);for(int k=len;k>=len-2&&k>0;k--)m[str.substr(0,k)]+=len-k+1;  //進行統計}//所有相同的字符串都存儲到m中了，找長度最長的并且有3個int ret=-1;for(auto& [str,k]:m){if(k>=3) ret=max(ret,(int)str.size());}return ret;}
};

方法二：分組循環+二分

統計每個獨立的相同字符子串的長度。?

如果字符x的最長字符串為L1，則其可以形成滿足條件的最長子串為：L1-2；

如果字符x的次長字符串為L2，則其可以形成滿足條件的最長子串為：

當L1==L2，最長子串是：L1-1；

當L1 > L2，最長子串是：L2；

匯總就是：min(L1-1，L2)。

如果字符x的第三長字符串為L3，則其可以形成滿足條件的最長子串為：L3

第四長就不需要考慮了，考慮第三長是因為如果三個子字符串的長度相等，長度就是L3。

class Solution {
public:int maximumLength(string s) {unordered_map<char ,vector<int>> m;int i=0,n=s.size();while(i<n){int start=i;while(i<n&&s[i]==s[start]) i++;m[s[start]].push_back(i-start);}int ret=0;for(auto& [ch,nums]:m ){sort(nums.begin(),nums.end(),greater());nums.push_back(0);   //向后面補上兩個數據是的數組長度永遠大于等于3nums.push_back(0);ret=max({nums[2],min(nums[1],nums[0]-1),nums[0]-2,ret});}return ret==0?-1:ret;}
};

2576. 求出最多標記下標

題解：排序+同向雙指針。返回值最大就是數組長度，這種情況就是數組一分為二，數據前半部分與后半部分一一對應；所以可以先對數組進行排序，使用一個指針指向數組中間位置，一個指向數組尾部，判斷中間位置數據的兩倍是否大于尾部數據，如果大于是一組，否則說明中間數據太大了，向前走找更小的數據。

class Solution {
public:int maxNumOfMarkedIndices(vector<int>& nums) {//先對數組進行排序，再使用同向雙指針int n=nums.size();sort(nums.begin(),nums.end());int l=n/2-1,r=n-1,ret=0;while(l>=0&&r>=n/2){if(2*nums[l]<=nums[r]){r--;ret++;}l--;}return ret*2;}
};

1898. 可移除字符的最大數目

題解：模擬+二分。如果直接進行挨個刪除效率太低，可以同個二分進行優化。先確定給刪除的個數，再驗證p是不是s的子序列即可。

class Solution {bool check(string s,string& p,vector<int>& removable,int x){for(int i=0;i<x;i++) s[removable[i]]='0';  //對被刪除的位置進行修改int n=s.size(),m=p.size();int j=0;for(int i=0;i<n&&j<m;i++)if(s[i]==p[j]) j++;return j==m;}public:int maximumRemovals(string s, string p, vector<int>& removable) {//如果一個個的進行移除效率太低了//可以使用二分進行優化int n=removable.size();int left=0,right=n+1;while(left+1<right){int mid=left+(right-left)/2;if(check(s,p,removable,mid)) left=mid;else right=mid;}return left;}
};

1802. 有界數組中指定下標處的最大值

題解：當直接進行求解比較難得時候考慮在已知答案得情況下能否進行驗證。此題如果直接進行求解比較復雜，如果已知index位置得最大數取判斷數組總和是否不超過maxSum就很簡單，求和時需要用到數列求和的公式。

class Solution {bool check(int n,int index,long long maxSum,long long t){long long l=index,r=n-index-1;long long all=0;if(t>l) all+=t*(t-1)/2-(t-l-1)*(t-l)/2;else all+=t*(t-1)/2+l-t+1;if(t>r) all+=t*(t-1)/2-(t-r-1)*(t-r)/2;else all+=t*(t-1)/2+r-t+1;return all+t<=maxSum;}public:int maxValue(int n, int index, int maxSum) {//直接進行模擬難度太大，如果已知最大值進行驗證就比較簡單了int left=0,right=maxSum+1;while(left+1<right){int mid=left+(right-left)/2;if(check(n,index,maxSum,mid)) left=mid;else right=mid;}return left;}
};

1642. 可以到達的最遠建筑

題解：在已知到達的高度的情況下，判斷磚和梯子是否夠即可；細節：為了找到最優解梯子應該使用在需要磚塊最多的位置，所以可以使用一個小堆找出使用最多的梯子。

class Solution {
public:int furthestBuilding(vector<int>& heights, int bricks, int ladders) {int n=heights.size();//先將每個房子之間的高度差進行統計vector<int> heidiff(n-1);for(int i=1;i<n;i++) if(heights[i]>heights[i-1]) heidiff[i-1]=heights[i]-heights[i-1];//進行判斷auto check=[&](int level){//模擬看能否到達level地方 level-1個間隔long long all=accumulate(heidiff.begin(),heidiff.begin()+level,0L);priority_queue<int,vector<int>,greater<int>> pq;  //找出ladders個最大的數for(int i=0;i<level&&ladders>0;i++) {if(pq.size()<ladders)pq.push(heidiff[i]);else if(pq.top()<heidiff[i]){pq.pop();pq.push(heidiff[i]);}}//進行求和long long more=0;while(!pq.empty()){more+=pq.top();pq.pop();}return all-more<=bricks;};int left=0,right=n;while(left+1<right){int mid=left+(right-left)/2;if(check(mid)) left=mid;else right=mid;}return left;}
};

2861. 最大合金數

題解：依舊是驗證答案。通過二分來確定答案，再對答案進行檢測即可。如果答案的預算太大right-mid，如果答案預算足夠left=mid即可。

class Solution {typedef long long LL;
public:int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {//判斷能否創建ret個合金auto check=[&](LL ret){for(auto& nums:composition){LL sum=0;for(int i=0;i<n;i++)sum+=cost[i]*max(ret*nums[i]-stock[i],(LL)0);if(sum<=budget) return true;}return false;};int left=0,right=1e8*2+1;  //注意此處上界的取值：及要靠你budegt好要考慮stockwhile(left+1<right){int mid=left+(right-left)/2;if(check(mid)) left=mid;else right=mid;}return left;}
};