题目链接：3281. 范围内整数的最大得分（中等）
算法原理：
解法：二分查找+贪心
60ms击败50.38%
时间复杂度O(Nlogn)
题目分析：一开始理解题意可能有些抽象，其实就是让我们找一个最大值，同时这个最大值是两数间的差值，我们在用二分找最大值mid时，判断这个最大值能否找的出来，也就是说这个最大值要在区间内
①目标变量：可能得分（最小绝对差）
②目标条件：在当前可能得分的情况下，能够保证可以从[start[i],start[i]+d]中恰好选一个数，使得所选整数两两间最小绝对值差≥最大得分，且这个最小绝对差要最大化
③转换逻辑：在当前最大可能得分为mid的情况下，能够保证可以从[start[i],start[i]+d]中恰好选一个数，使得所选整数两两间最小绝对值差≥mid
具体步骤：
①确定边界：
left：0，所有数选同一个值，最小差为0
right：start[n-1]+d-start[0]，排序后，第一个数选最左端点，最后一个数选最右端点，二者差即为最大差值
②确定二分模型：可能得分 ↑ 能落在区间概率 ↓ 各区间恰好选一个数 ↓ 条件符合率 ↓ 成负相关单调，由于要找最大的最小绝对查，因此采用最右端点模型
③check方法设计：
采用贪心策略：在满足条件的前提下，每个数选的越小越好，为后续区间留更大选择空间，防止越界
第一个数直接选当前区间左端点start[0]
第二个数及以后必须满足两个条件
1.≥前一个数+mid，因为要保证与前一个数的差≥mid
2.≥当前区间左端点start[i]，因为必须落在区间内
然后取同时满足两条件的最小值，如果这个最小值≤右区间端点，说明不越界，能选，否则就是该区间选不到数，直接返回false
Java代码：
class Solution {
public int maxPossibleScore(int[] start, int d) {
Arrays.sort(start);
int n=start.length;
//最大可能得分=最右端点-最左端点
int left=0,right=start[n-1]+d-start[0];
while(left<right){
int mid=left+(right-left+1)/2;
if(!check(mid,start,d)) right=mid-1;
else left=mid;
}
return left;
}
private boolean check(int mid,int[] start,int d){
int n=start.length;
//贪心策略：第一个数选区间左端点，给后续留最大选择空间
long prev=start[0];
for(int i=1;i<n;i++){
//①当前数必须比上个数大mid，保证相邻差≥mid
//②当前数必须在区间内，不能小于区间左端点start[i]
//取①和②的最大值以保证满足①②
long cur=Math.max(prev+mid,start[i]);
//如果超过区间右端点，说明mid不可行
if(cur>start[i]+d) return false;
prev=cur;//更新prev，处理后续区间
}
return true;
}
}
