题目链接1802. 有界数组中指定下标处的最大值中等算法原理解法二分查找1ms击败91.18%时间复杂度O (log (maxSum))①目标变量nums[index]的取值②目标条件nums[index]取值最大且满足数组两边最小递减至1的和≤maxSum③转换逻辑取值为nums[mid]时是否满足数组两边最小递减至1的和≤maxSum具体步骤①确定边界left1因为题目要求nums[i]是正整数因此最小值是1rightmaxSum②确定二分模型nums[mid]↑ 条件符合率↓ 呈负相关单调由于是找到最大的nums[mid]因此采用最右端点模型③check方法设计记L和R为index左侧和右侧元素个数和则有下图关系因此我们在计算数组总和时分三个部分来算总和左mid右以计算左侧和为例右侧与之相同1.可连续递减时用等差数列求和项数nL,首项挨着mid的a1mid-1,末项anmid-L因此2.不可连续递减时减至1后后续都是1递减部分从1加到n的和有个经典公式代入nmid-1后得到后续非递减部分从1到mid-1共有mid-1个数因此剩下L-(mid-1)个数这些都是1所以最终式子为Java代码class Solution { public int maxValue(int n, int index, int maxSum) { int left1,rightmaxSum; while(leftright){ int midleft(right-left1)/2; if(!check(n,mid,maxSum,index)) rightmid-1; else leftmid; } return left; } //判断nums[index]mid时是否符合条件 private boolean check(int n,int mid,int maxSum,int index){ //先算上中间元素 long summid; int Lindex;//左边元素个数 int Rn-1-index;//右边元素个数 //计算左边和:不可连续递减就递减到1后保持1 if(mid-1L) sum(long)L*(2*mid-1-L)/2; else sum(long)(mid-1)*mid/2(L-(mid-1)); //计算右边和:逻辑与左边一致 if(mid-1R) sum(long)R*(2*mid-1-R)/2; else sum(long)(mid-1)*mid/2(R-(mid-1)); return summaxSum; } }