题目1802. 有界数组中指定下标处的最大值

题面

给你三个正整数 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 。

关键词

二分

思路

整体思路是二分nums[index]，设其为target，初始下界leftborder为1，上界rightborder为maxSum，看[0……index]区间的和加上[index …… n-1]区间的和比maxSum要大还是小，大的话令rightborder-1，小的话令leftborder+1.

基本前提是，如果下标index处的值为target，

那么[0……index]区间的值有两种情况：

• 1 2 3 …… target-2 target-1 target
• target-index target-index+1 target-index+2 …… target

同样[index …… n-1]区间也分为两种情况：

• target target-1 …… target - (n-index-1)
• target target-1 …… 2 1

代码

class Solution {
public:int maxValue(int n, int index, int maxSum) {//左区间和、右区间和、总和long int leftsum,rightsum,sum;//左边界、右边界long int leftborder,rightborder;leftborder = 1;rightborder = maxSum;//nums[index]处的值long int target;//二分查找while(leftborder<=rightborder){target = (leftborder+rightborder)/2;//左区间的两种情况的和if(target>index)leftsum = (2*target-index)*(index+1)/2;elseleftsum = (1+target)*target/2+(index-target+1);//右区间的两种情况的和if(target>(n-index))rightsum = (target*2-n+index+1)*(n-index)/2;elserightsum = (1+target)*target/2+(n-index-target);//减去target是因为左右区间计算了两次nums[target]的值sum = leftsum+rightsum-target;// cout<<"leftboreder: "<maxSum)rightborder = target-1;else if(summaxSum)return target-1;elsereturn target;}
};

总结

看了题目下面的提示才有的二分的思路，还要继续努力。

分情况讨论target与左右边界的关系还是比较麻烦，看评论区有比较巧妙的思路，不知道能不能学会。

参考