D.二分查找－二分答案－求最大——1802. 有界数组中指定下标处的最大值

题目链接：1802. 有界数组中指定下标处的最大值（中等）

算法原理：

解法：二分查找

1ms击败91.18%

时间复杂度O (log (maxSum))

①目标变量：nums[index]的取值

②目标条件：nums[index]取值最大，且满足数组两边最小递减至1的和≤maxSum

③转换逻辑：取值为nums[mid]时，是否满足数组两边最小递减至1的和≤maxSum

具体步骤：

①确定边界：

left：1，因为题目要求nums[i]是正整数，因此最小值是1

right：maxSum

②确定二分模型：nums[mid]↑ 条件符合率↓ 呈负相关单调，由于是找到最大的nums[mid]，因此采用最右端点模型

③check方法设计：

记L和R为index左侧和右侧元素个数和，则有下图关系：

因此我们在计算数组总和时分三个部分来算：总和=左+mid+右

以计算左侧和为例（右侧与之相同）：

1.可连续递减时：用等差数列求和

项数n=L,首项（挨着mid的）a1=mid-1,末项an=mid-L，因此

2.不可连续递减时（减至1后，后续都是1）：

递减部分：从1加到n的和有个经典公式，代入n=mid-1后得到

后续非递减部分：从1到mid-1共有mid-1个数，因此剩下L-(mid-1)个数，这些都是1

所以最终式子为

Java代码：

class Solution { public int maxValue(int n, int index, int maxSum) { int left=1,right=maxSum; while(left<right){ int mid=left+(right-left+1)/2; if(!check(n,mid,maxSum,index)) right=mid-1; else left=mid; } return left; } //判断nums[index]=mid时是否符合条件 private boolean check(int n,int mid,int maxSum,int index){ //先算上中间元素 long sum=mid; int L=index;//左边元素个数 int R=n-1-index;//右边元素个数 //计算左边和:不可连续递减就递减到1后保持1 if(mid-1>=L) sum+=(long)L*(2*mid-1-L)/2; else sum+=(long)(mid-1)*mid/2+(L-(mid-1)); //计算右边和:逻辑与左边一致 if(mid-1>=R) sum+=(long)R*(2*mid-1-R)/2; else sum+=(long)(mid-1)*mid/2+(R-(mid-1)); return sum<=maxSum; } }