目录
一、题目描述 1802. 有界数组中指定下标处的最大值
二、实现思路以及代码
一、题目描述 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
示例 1：
输入：n = 4, index = 2, maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。
示例 2：
输入：n = 6, index = 1, maxSum = 10
输出：3二、实现思路以及代码
思路：
注意要求返回所构造的数组中的 nums[index] ，返回的是数组中的nums[index]值。体重nums的条件最后一条是 nums[index] 的值被 最大化，故在保证其他条件条件下，要尽量保证index处的值最大。
如何保证index处的值最大化，我们可以把题目模拟建设一座高塔，index位置就是塔尖所在位置，我们自底层开始一层一层的堆积塔。开始第一层时，我们把长度为n的数组全部平铺满一层，用去n个数，最多还可以使用 maxSum - n 个数。紧接着开始堆积第二层，我们优先在index处堆积，则第二层可以1个数（只在index处放一个数）。紧接着堆积第三层，仍然是先堆积index位置处，为了把第二层堆积的元素“包裹”住，最多可以有3个数。同理堆积第四层，“包裹”第三层添加的元素，最多可以有5个数。依次类推，在不超过两边的边界的情况下，每层可以添加的元素个数addNum为right - left +1 (其中left指向包裹放一层元素可以放在最右边的位置，left指向包裹放一层元素可以放在最做边的位置)。
那么我们做如下操作，每次堆积层数时，判断最大可使用的元素个数testNum是否大于可以添加的元素个数addNum。若大于等于，则直接累加一层，最大可使用元素testNum的值需要减去addNum;否则 剩余可以使用的元素堆积当前层。最后返回nuns[index]。
实现代码：
class Solution {public int maxValue(int n, int index, int maxSum) {int left = index, right = index;// 左右指针向两边扩散int res = 1; //结果集,开始平铺一层，故初始化nums[index]=1// 开始时让数组中每个元素都等于1，保证nums[i] 是 正整数int testNum = maxSum - n; //平铺一层后，剩余最多可以使用的元素。while (left > 0 || right < n - 1) {int addNum = right - left + 1; //向上堆积一层可以添加的元素个数if (testNum >= addNum) {// 剩余个数大于叠加一层序添加的个数res++;testNum = testNum - addNum;// 两边指针往外扩充left = Integer.max(0, left - 1);right = Integer.min(n - 1, right + 1);} else {//网上累积一层添加的个数大于可以使用的个数，值接退出循环break;}}// 若有剩余的元素，此时已经不能往两边扩充，只能向上堆积元素，// 此时向上堆积一层的元素个数固定，为数组的长度n。//判断剩余元素中最多包含有多少个n,即可以再往上累加多少层。res += testNum / n;return res;}
}