给你三个正整数 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 。
过程模拟，从index开始往两边扩充：维护一个[l,r]范围，每次往范围内每个位置+1，通过这种方式维护一个向上生长的“三角形”。
时间复杂度O(logM)，其中M为maxSum-n。
空间复杂度O(1)。
对于
减少1 + 3 + 5 + ... 直到 剩余不够 假设共n+1项M = maxSum - n
, 有1 + 3 + 5 ... + (2n + 1) = (n + 1)(1 + 2n + 1) /2 = (n + 1) ^2
所以(n + 1)^2 < M
, 时间复杂度为n = log2(M)
O(log2(M))
public int maxValue(int n, int index, int maxSum) {
int l = index, r = index;
int ans = 1;
// 整个数组一开始全部填充为1，
// rest记录先全部填充1后，剩下1的个数
int rest = maxSum - n;
while (l > 0 || r < n - 1) {
int len = r - l + 1;
if (rest >= len) {
// 当前[l,r]范围全部+1
rest -= len;
ans++;
// 往左右两边扩
l = Math.max(0, l - 1);
r = Math.min(n - 1, r + 1);
} else {
break;
}
}
// 扩大到整个数组之后，剩余的值“雨露均沾”一下
ans += rest / n;
return ans;
}
作者：liberg
链接：https://leetcode-cn.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/solution/shu-xue-guo-cheng-mo-ni-zui-qing-xi-de-j-gz30/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
把每一个数当成一个砖块，目的是堆成形如三角形的台阶，使index所在处的台阶尽可能高。
本解法未使用任何算法，只是简单粗暴的模拟堆台阶的过程，毕竟菜鸡什么算法也不会啊😭😭。
class Solution {
public:
int maxValue(int n, int index, int maxSum) {
int diff=maxSum-n,left=index,right=index, res=1,dl=0,dr=0;
while(diff>0){ //当还有剩余砖块时
if(--left>=0) dl++; //尚未到达左边界
if(++right<n) dr++; //尚未到达右边界
if(left<0&&right>=n){ //当到达左边界和右边界时 及时退出
res+=diff%n==0?diff/n:diff/n+1; //把剩余的砖块均分了，直接退出
return res;
}
res+=1; //层数更新
diff-=(dl+dr+1); //使顶层堆成严格正三角形所需的砖块数(左边所需+右边所需+index处1个)
}
return res;
}
};
作者：ivon_shi-a-feng-ya
链接：https://leetcode-cn.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/solution/jian-dan-mo-ni-jiu-ceng-zhi-tai-qi-yu-le-c6f6/
很明显 为使的值最大，需要使每一列的顶层其尽可能形成为一个严格的三角形（阶梯式），即从num[index]
向两边单调递减。index
否则，要么不满足要求
或者产生浪费（当然为了使之后堆的更高也可看作不算浪费）
模拟从底层向上堆砖块，当在index处添加砖块可以满足要求时，添加即可。
当想在index出添加砖块，却不满足要求时，需要先把周围的方块组成的台阶堆起来。
那么问题 是需要多少块才能把周围堆成台阶呢？
#对于一般情况：
1.由于maxSum>=n,故每列都能先安排一块砖；剩余砖块数为diff=maxSum-n
2.先堆完一层后，先往index处堆，再往其附近依次堆，左右两个方向同时推进 直到边界
（dl表示堆下一层时 所需要的左侧砖块数目，dr表示堆下一层时 所需要的右侧砖块数目）
（新颜色表示的砖块 代表 每堆高一层（下一层）所需要周围预先布置好的砖块数，左边为dl=1，右边为dr=1）
（左边为dl=2，右边为dr=2）
#对于特殊情况（边界情况）：
1.单边：
对于左边或右边已经到达边界，为使index处的高度增加，每增加一层，不再需要该侧更多的砖块，保持dl或dr即可，此时只有某一侧的顶层，满足严格的三角形，而未到达边界的一侧继续推进。
（左边为dl=3，右边为dr=3）
（左边为dl=3，右边为dr=4）
2.双边：
当两边都已经达到边界，为使index处的高度继续增加，每增加一层，只需要固定数目的砖块数量即可，此时（对于每一列的顶层，已经满足严格的三角形），可以直接将剩余砖块瓜分**（否则会超时）**，其中index处分得砖块数量最多或至少与其他列相同，根据是否可以平均分配，index列可以增加的高度为 diff%n==0?diff/n:diff/n+1。
（左边为dl=3，右边为dr=5，之后 dl，dr值均保持不变）
class Solution {
public int maxValue(int n, int index, int maxSum) {
int diff=maxSum-n,left=index,right=index, res=1,dl=0,dr=0;
while(diff>0){ //当还有剩余砖块时
if(--left>=0) dl++; //尚未到达左边界
if(++right<n) dr++; //尚未到达右边界
if(left<0&&right>=n){ //当到达左边界和右边界时 及时退出
res+=diff%n==0?diff/n:diff/n+1; //把剩余的砖块均分了，直接退出
return res;
}
res+=1; //层数更新
diff-=(dl+dr+1); //使顶层堆成严格正三角形所需的砖块数(左边所需+右边所需+index处1个)
}
return res;
}
}
作者：ivon_shi-a-feng-ya
链接：https://leetcode-cn.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/solution/jian-dan-mo-ni-jiu-ceng-zhi-tai-qi-yu-le-c6f6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。