1.题目基本信息
1.1.题目描述
给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：
- nums.length == n
- nums[i] 是 正整数 ，其中 0 <= i < n
- abs(nums[i] – nums[i+1]) <= 1 ，其中 0 <= i < n-1
- nums 中所有元素之和不超过 maxSum
- nums[index] 的值被 最大化
- 返回你所构造的数组中的 nums[index] 。
注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。
1.2.题目地址
https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/description/
2.解题方法
2.1.解题思路
nums[index]越小，numsSum越小，通过该单调性可以进行二分查找nums[index]
2.2.解题步骤
第一步，确定二分的对象，由于numsSum随nums[index]单调递增，所以可以对nums[index]作为二分对象，numsSum作为二分的判断条件
第二步，确认红蓝染色的条件。红：nums[index]的条件下，numsSum<=maxSum，蓝：numsSum>maxSum。左闭右闭：left-1始终指向红色，right+1始终指向蓝色。最终的right为题解
第三步，构建check函数，这里的check函数判断nums[index]为indexVal条件下，贪心构建的数组和是否小于等于maxSum。同时在计算和的方法采用部分等差数列求和的方式，减少计算量，如果采用循环遍历求和，会超时
第四步，采用标准的红蓝染色的左闭右闭模板进行解题，最终的right即为题解
3.解题代码
Python代码
class Solution:def maxValue(self, n: int, index: int, maxSum: int) -> int:# nums[index]越小，numsSum越小，通过该单调性可以进行二分查找nums[index]# 第一步，确定二分的对象，由于numsSum随nums[index]单调递增，所以可以对nums[index]作为二分对象，numsSum作为二分的判断条件# 第二步，确认红蓝染色的条件。红：nums[index]的条件下，numsSum<=maxSum，蓝：numsSum>maxSum。左闭右闭：left-1始终指向红色，right+1始终指向蓝色。最终的right为题解# 第三步，构建check函数，这里的check函数判断nums[index]为indexVal条件下，贪心构建的数组和是否小于等于maxSum。同时在计算和的方法采用部分等差数列求和的方式，减少计算量，如果采用循环遍历求和，会超时# 第四步，采用标准的红蓝染色的左闭右闭模板进行解题，最终的right即为题解def calcSum(maxVal,length):# 计算最大值为maxVal，长度为length的序列的和，序列满足从maxVal开始逐渐递减，直到为1，并维持为1if maxVal>=length:# 等差数列求和sum1=length*(maxVal+(maxVal-length+1))//2else:sum1=maxVal*(maxVal+1)//2+length-maxValreturn sum1def check(indexVal):sum_=calcSum(indexVal,index+1)+calcSum(indexVal,n-index)-indexValreturn sum_<=maxSumleft,right=1,maxSumwhile left<=right:mid=(right-left)//2+leftif check(mid):# nums[index]为mid时，贪心的numsSum<=maxSumleft=mid+1else:right=mid-1return right
4.执行结果
