参考资料来源灵神在力扣所发的题单，仅供分享学习笔记和记录，无商业用途。
核心思路：本质上是求最小
应用场景：在满足条件的最大值区间内使最小化
模板：
bool check() //检查条件
int smallestDivisor(vector<int>& nums, int threshold) {
while(l<r){ //二分搜索答案
mid=l+((r-l)>>1);
if(check(nums,mid,threshold)){ //满足条件，缩小区间尝试找到更好数据
r=mid; //记录答案
}else l=mid+1; //不满足条件，扩大区间积极找到合法答案
}
return l;力扣题单练习(灵神题单中摘取题目)
题意：将数组划分成k个子数组，求子数组各自和的最大值最小化。
思路：
合理右边界:假设划分成1个子数组，数组区间和值则为最大值，由于只有一个子数组所以也是最小
检查函数：判断数组是否能划分成k个满足区间和小于等于目标值的子数组
遍历数组当累加当前数据大于目标值则划分前面区间为一个子数组
class Solution {
public:
//检查函数：判断数组是否能划分成k个满足区间和小于等于目标值的子数组
//遍历数组当累加当前数据大于目标值则划分前面区间为一个子数组
bool check(vector<int> nums, int k, int ret){
int buff=0,part=0;
for(int i=0;i<nums.size();i++){
if(nums[i]>ret) return false; //出现单个元素大于目标值，并且元素都为正整数，说明不管这怎么划分子数组至少一个不能满足条件
if(buff+nums[i]>ret){ //区间和大于目标值则重置数据为当前元素，并且对区间数量进行累加
part++;
buff=nums[i];
}else buff+=nums[i]; //继续累加到最大合法区间
if(part>=k) return false; //当前划分区间数量大于k个说明目标值设立过小，需要调大
}
return true;
}
int splitArray(vector<int>& nums, int k) {
//题意：将数组划分成k个子数组，求子数组各自和的最大值最小化。
//合理右边界:假设划分成1个子数组，数组区间和值则为最大值，由于只有一个子数组所以也是最小
int l=INT_MIN,r=0,mid;
for(auto x:nums){
r+=x;
l=max(l,x);
}
while(l<r){
mid=l+((r-l)>>1);
if(check(nums,k,mid)) r=mid;
else l=mid+1;
}
return l;
}
};题意：
有n家商店和m种产品、数量数组。一家商店只能接受一种产品，无数量限制。
求所有商店分配商品数目的最大值(可不必达到此数量)最小化，要求把m种产品的数量数组全部分配完。
思路：
合理右边界：因为m<=n，所以能保证m种产品能全部分配到位。选取数量数组的最大值
检查函数：判断商品数量数组是否能以最大值为k数量并且商店选择一种商品分配的方式全部分配给n个商店
如果以最大值方式进行分配的数量大于n，说明以当前最大值方式不管怎么分配都无法分配完所有数量
class Solution {
public:
//检查函数：判断商品数量数组是否能以最大值为k数量并且商店选择一种商品分配的方式全部分配给n个商店
//如果以最大值方式进行分配的数量大于n，说明以当前最大值方式不管怎么分配都无法分配完所有数量
bool check(vector<int>& quantities, int k, int n){
for(int i=0;i<quantities.size();i++) n-=(quantities[i]+k-1)/k;
return n>=0;
}
int minimizedMaximum(int n, vector<int>& quantities) {
//题意：有n家商店和m种产品、数量数组。一家商店只能接受一种产品，无数量限制。
//求所有商店分配商品数目的最大值(可不必达到此数量)最小化，要求把m种产品的数量数组全部分配完。
//合理右边界：因为m<=n，所以能保证m种产品能全部分配到位。选取数量数组的最大值
int l=1,r=0,mid;
for(int i=0;i<quantities.size();i++) r=max(r,quantities[i]);
while(l<r){
mid=l+((r-l)>>1);
if(check(quantities,mid,n)) r=mid;
else l=mid+1;
}
return l;
}
};题意：给定一个数组，其中数组最大值为开销，给定k次操作，可以将一个数拆开为两个数。要求最小开销
思路：
合理右边界：假设不使用操作，设置数据中最大值作为右边界为极端情况
检查函数：判断数组是否都能小于等于n
数学思维：将x拆为最大值为n的最小拆开次数=(x-1)/n
class Solution {
public:
//检查函数：判断数组是否都能小于等于n
bool check(vector<int>& nums, int k, int n){
for(auto x: nums){
if(x<=n) continue;
k-=(x-1)/n; //计算x拆开成最大值为n的数组的最小拆开次数(尽量将数组中的元素为n)
}
return k>=0;
}
int minimumSize(vector<int>& nums, int maxOperations) {
//题意：给定一个数组，其中数组最大值为开销，给定k次操作，可以将一个数拆开为两个数。要求最小开销
//合理右边界：假设不使用操作，设置数据中最大值作为右边界为极端情况
int l=1,r=INT_MIN,mid;
for(auto x: nums) r=max(r,x);
while(l<r){
mid=l+((r-l)>>1);
if(check(nums,maxOperations,mid)) r=mid;
else l=mid+1;
}
return l;
}
};题意：给定一个二维地图，一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值决定的。求最小体力消耗值
思路：
合理右边界：选取图中最大绝对差值作为极端边界
dfs模板搜索：不走遍历过的路，并且不走不满足高度差绝对值>k的路，搜索到满足条件并且到达终点则true
class Solution {
public:
int d[4][2]={0,-1,0,1,-1,0,1,0};
//dfs模板搜索：不走遍历过的路，并且不走不满足高度差绝对值>k的路，搜索到满足条件并且到达终点则true
bool dfs(vector<vector<int>>& heights,vector<vector<bool>>& vis, int k,int x,int y){
if(x==heights.size()-1 && y==heights[0].size()-1) return true;
vis[x][y]=true;
for(int i=0;i<4;i++){
int c=x+d[i][0];
int v=y+d[i][1];
if(c<0 || c>=heights.size() || v<0 || v>=heights[0].size() || vis[c][v] || abs(heights[x][y]-heights[c][v])>k) continue;
if(dfs(heights,vis,k,c,v)) return true;
}
return false;
}
int minimumEffortPath(vector<vector<int>>& heights) {
//题意：给定一个二维地图，一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值决定的。求最小体力消耗值
//合理右边界：选取图中最大绝对差值作为极端边界
int l=0,r=INT_MAX,mid=INT_MIN;
for(int i=0;i<heights.size();i++){
for(auto x:heights[i]){
r=min(r,x);
mid=max(mid,x);
}
}
r=abs(r-mid);
while(l<r){
mid=l+((r-l)>>1);
vector<vector<bool>> vis(heights.size(),vector<bool>(heights[0].size(),false));
if(dfs(heights,vis,mid,0,0)) r=mid;
else l=mid+1;
}
return l;
}
};题意：给定一个数组，可以进行任意次给当前元素-1，前一个元素+1操作。求最小化最大值
思路：
合理右边界：设置当前数组中最大值作为极限边界。
检查函数：判断原数组进行多次操作后是否满足最大值为k。
贪心原理：反向遍历数据，记录前一位的更变值，当前元素+更变值<=k说明当前元素无需操作，也就是下一个元素的更变值为0。反之亦然
在贪心操作下，第二个元素~最后一个元素都是<=k，只需要判断第一个元素为前一位准备的更变值是否为0即可
class Solution {
public:
//检查函数：判断原数组进行多次操作后是否满足最大值为k。
//贪心原理：反向遍历数据，记录前一位的更变值，当前元素+更变值<=k说明当前元素无需操作，也就是下一个元素的更变值为0。反之亦然
//在贪心操作下，第二个元素~最后一个元素都是<=k，只需要判断第一个元素为前一位准备的更变值是否为0即可
bool check(vector<int>& nums, int k){
long long cnt=0;
for(int i=nums.size()-1;i>=0;i--){
if(nums[i]+cnt<=k){
cnt=0;
continue;
}
cnt=nums[i]+cnt-k;
}
return cnt==0;
}
int minimizeArrayValue(vector<int>& nums) {
//题意：给定一个数组，可以进行任意次给当前元素-1，前一个元素+1操作。求最小化最大值
//合理右边界：设置当前数组中最大值作为极限边界。
int l=0,r=INT_MIN,mid;
for(auto x:nums) r=max(r,x);
while(l<r){
mid=l+((r-l)>>1);
if(check(nums,mid)) r=mid;
else l=mid+1;
}
return l;
}
};力扣灵神题单2000分以下二分答案求最大已完成，后续会更新2000+的专题。