參考資料來源靈神在力扣所發的題單，僅供分享學習筆記和記錄，無商業用途。

核心思路：本質上是求最大

應用場景：在滿足條件的最小值區間內使最大化

檢查函數：保證數據都要大于等于答案

補充：為什么需要滿足大于等于答案的元素而不是等于答案的元素，因為二分會收斂至最優結果

模板：

    bool check() //檢查條件int smallestDivisor(vector<int>& nums, int threshold) {while(l<r){mid=l+((r-l)>>1)+1;if(check(start,d,mid)) l=mid; //滿足條件，增大區間嘗試找到更好數據else r=mid-1;  //不滿足條件，縮小區間積極找到合法答案}return l;

力扣題單練習(靈神題單中摘取題目)

3281. 范圍內整數的最大得分

題意：

給定一個整數數組表示有n個區間[start[i], start[i] + d]。

要求在每個區間內選取一個數，然后這些數據進行兩兩組合進行絕對差計算，以最小絕對差為結果

要求怎樣在區間內取數讓結果最大化，也就是最小絕對差最大化

思路：

合理右邊界：選取整數數組中最小值和最大值+d獲得最大絕對差

檢查函數：判斷當前區間對每個區間各取的整數的絕對差是否都大于等于答案。

貪心策略：當區間左邊界+答案，小于等于下一個區間右邊界說明絕對差值大于等于答案，當前成立。

貪心補充：

因為是升序，所以滿足了后一個區間，后面所有區間絕對差值只會越來越大，所以當前成立。

采用當前區間左邊界是因為要讓它盡可能落到合法區間，如果它都沒有滿足，當前區間內所有數據都不會滿足。

反之說明當前答案不成立，因為至少有一組區間的絕對差小于答案。

class Solution {
public://檢查函數：判斷當前區間對每個區間各取的整數的絕對差是否都大于等于答案。//貪心策略：當區間左邊界+答案，小于等于下一個區間右邊界說明絕對差值大于等于答案，當前成立。//因為是升序，所以滿足了后一個區間，后面所有區間絕對差值只會越來越大，所以當前成立。//采用當前區間左邊界是因為要讓它盡可能落到合法區間，如果它都沒有滿足，當前區間內所有數據都不會滿足//反之說明當前答案不成立，因為至少有一組區間的絕對差小于答案。bool check(vector<int>& nums, int d, int ret){long long x = LLONG_MIN;for(long long k:nums){x=max(k,x+ret);if(x>k+d) return false;  //超出下一個區間右邊界說明至少存在一組區間的絕對差小于答案，不滿足}return true;}int maxPossibleScore(vector<int>& start, int d) {//題意：給定一個整數數組表示有n個區間[start[i], start[i] + d]。//要求在每個區間內選取一個數，然后這些數據進行兩兩組合進行絕對差計算，以最小絕對差為結果//要求怎樣在區間內取數讓結果最大化，也就是最小絕對差最大化//合理右邊界：選取整數數組中最小值和最大值+d獲得最大絕對差sort(start.begin(),start.end());int l=0,r=start[start.size()-1]-start[0]+d,mid;while(l<r){mid=l+((r-l)>>1)+1;if(check(start,d,mid)) l=mid;else r=mid-1;}return l;}
};

2517. 禮盒的最大甜蜜度

題意：

給定一個正整數數組，要求你選取k個元素，并求出任意兩元素絕對差的最小值，要求最小值最大化

思路：

合理右邊界：最大可能的差值是最大值減最小值

檢查函數：選取排序后第一個元素，判斷是否有k個滿足大于等于答案的元素

貪心策略：如果最小值作為選取值都沒有找到滿足條件的k個元素，其他更不可能

class Solution {
public://檢查函數：選取排序后第一個元素，判斷是否有k個滿足大于等于答案的元素//為什么需要滿足大于等于答案的元素而不是等于答案的元素，因為二分會收斂至最優結果//貪心策略：如果最小值作為選取值都沒有找到滿足條件的k個元素，其他更不可能bool check(vector<int>& nums, int k, int ret){int cnt=1; //選取數據的數量int last=nums[0];  //當前選取元素for(int i=1;i<nums.size();i++){if(nums[i]-last>=ret){last=nums[i];cnt++;if(cnt==k) return true; //當滿足條件的元素等于k個時，說明答案成立}}return false;}int maximumTastiness(vector<int>& price, int k) {//題意：給定一個正整數數組，要求你選取k個元素，并求出任意兩元素絕對差的最小值，要求最小值最大化//合理右邊界：最大可能的差值是最大值減最小值sort(price.begin(),price.end());int l=0,r=price.back()-price[0],mid;while(l<r){mid=l+((r-l)>>1)+1;if(check(price,k,mid)) l=mid;else r=mid-1;}return l;}
};

2812. 找出最安全路徑

題意：

給定一個大小為 n x n 的二維矩陣 grid。

grid[r][c] = 1 ，則表示一個存在小偷的單元格。grid[r][c] = 0 ，則表示一個空單元格

你最開始位于單元格 (0, 0)，可以上下左右移動。返回所有通向單元格 (n - 1, n - 1) 的路徑中的 最大安全系數 。

安全系數 定義為：從路徑中任一單元格到矩陣中任一小偷所在單元格的 最小 曼哈頓距離。

兩個單元格 (a, b) 和 (x, y) 之間的 曼哈頓距離 等于 | a - x | + | b - y | 。

思路：

合理右邊界：

安全系數定義為路徑上任意點到最近小偷的最小曼哈頓距離。

對于一個n×n的矩陣，任意兩點間的最大曼哈頓距離為2n-2（從左上角到右下角）。但由于小偷可能位于矩陣內部，實際的安全系數上限會更小。

在最壞情況下，小偷位于四個角落，安全系數最大為n-1，此時右邊界設為n（即矩陣行長度）可以覆蓋所有可能的安全系數。

檢查函數：判斷是否有一條到達終點且路徑上的單元格到小偷單元格距離大于等于答案的路徑

class Solution {
public:int d[4][2]={0,1,0,-1,-1,0,1,0};//檢查函數：判斷是否有一條到達終點且路徑上的單元格到小偷單元格距離大于等于答案的路徑bool check(vector<vector<int>>& dist, int k){if(dist[0][0]<k) return false;  vector<vector<bool>> vis(dist.size(),vector<bool>(dist[0].size(),false)); //去重queue<pair<int,int>> q;vis[0][0]=true;q.push({0,0});while(!q.empty()){  //廣搜：在所有到達終點的路徑中找到一條滿足條件的路徑auto [x,y]=q.front();q.pop();for(int m=0;m<4;m++){int i=x+d[m][0];int j=y+d[m][1];if( i<0 || i>=dist.size() || j<0 || j>=dist[0].size() || dist[i][j]<k || vis[i][j]) continue;if(i==dist.size()-1 && j==dist[0].size()-1) return true;vis[i][j]=true;q.push({i,j});}}return false;}int maximumSafenessFactor(vector<vector<int>>& grid) {//題意：給定一個大小為 n x n 的二維矩陣 grid。//grid[r][c] = 1 ，則表示一個存在小偷的單元格。grid[r][c] = 0 ，則表示一個空單元格//你最開始位于單元格 (0, 0)，可以上下左右移動。返回所有通向單元格 (n - 1, n - 1) 的路徑中的 最大安全系數 。//安全系數 定義為：從路徑中任一單元格到矩陣中任一小偷所在單元格的 最小 曼哈頓距離。//兩個單元格 (a, b) 和 (x, y) 之間的 曼哈頓距離 等于 | a - x | + | b - y | 。//合理右邊界：安全系數定義為路徑上任意點到最近小偷的最小曼哈頓距離。//對于一個n×n的矩陣，任意兩點間的最大曼哈頓距離為2n-2（從左上角到右下角）。但由于小偷可能位于矩陣內部，實際的安全系數上限會更小。//在最壞情況下，小偷位于四個角落，安全系數最大為n-1，此時右邊界設為n（即矩陣行長度）可以覆蓋所有可能的安全系數。vector<vector<int>> dist(grid.size(),vector<int>(grid[0].size(),-1));queue<pair<int,int>> q;//記錄小偷所在單元格的位置，并重置距離for(int i=0;i<grid.size();i++){for(int j=0;j<grid[0].size();j++){if(grid[i][j]==1){q.push({i,j});dist[i][j]=0;}}}//計算每個普通單元格距離小偷單元格的最小距離while(!q.empty()){auto [x,y]=q.front();q.pop();for(int m=0;m<4;m++){int i=x+d[m][0];int j=y+d[m][1];if(i<0 || i>=dist.size() || j<0 || j>=dist[0].size()) continue;if(dist[i][j]==-1){dist[i][j]=dist[x][y]+1;q.push({i,j});}}}int l=0,r=grid[0].size(),mid;while(l<r){mid=l+((r-l)>>1)+1;if(check(dist,mid)) l=mid;else r=mid-1;}return l;}
};

2528. 最大化城市的最小電量

題意：

給定一個整數數組表示每個城市的供電站數量和影響范圍。可以額外添加k座供電站

每個供電站可以在一定范圍內給所有城市提供電力。要求城市最小電量最大化

思路：

合理右邊界：城市最小電量+k為極限邊界

檢查函數：判斷添加k個供電站是否能使數組元素都>=答案

貪心策略：如果當前城市電量小于答案，需要在當前位置+r，也就是右邊界添加。這樣能保證盡可能的輻射更多的城市

滑動窗口：維護區間內添加的發電站的總電量

class Solution {
public://檢查函數：判斷添加k個供電站是否能使數組元素都>=答案//貪心策略：如果當前城市電量小于答案，需要在當前位置+r，也就是右邊界添加。這樣能保證盡可能的輻射更多的城市//滑動窗口：維護區間內添加的發電站的總電量bool check(vector<long long>& nums, int r, int k, long long m){long long cnt=k;  //格外發電站建立數量long long buff=0; //當前位置+r區間內格外建造的發電站的總電量int n=nums.size();vector<long long> ans(n,0);for(int i=0;i<n;i++){if(i-r-1>=0) buff-=ans[i-r-1];  //維護一個定長滑窗long long total=buff+nums[i];if(total>=m) continue;long long need=m-total;if(cnt<need) return false;ans[min(i+r,n-1)]+=need;buff+=need;cnt-=need;}return true;}long long maxPower(vector<int>& stations, int r, int k) {//題意：給定一個整數數組表示每個城市的供電站數量和影響范圍。可以額外添加k座供電站//每個供電站可以在一定范圍內給所有城市提供電力。要求城市最小電量最大化//合理右邊界：城市最小電量+k為極限邊界int n=stations.size();vector<long long> buff(n+1,0);for(int i=0;i<n;i++) buff[i+1]=buff[i]+stations[i]; //計算前綴和//根據每個城市的供電站數量和影響范圍獲取城市的電量vector<long long> ans(n);long long min_num=LLONG_MAX;for(int i=0;i<n;i++){int left=max(i-r,0);int right=min(i+r,n-1);ans[i]=buff[right+1]-buff[left];min_num=min(min_num,ans[i]);}//二分答案long long head=0,tail=min_num+k,mid;while(head<tail){mid=head+((tail-head)>>1)+1;if(check(ans,r,k,mid)) head=mid;else tail=mid-1;}return head;}
};