难度: Medium
给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：
nums.length == nnums[i] 是 正整数 ，其中 0 <= i < nabs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1nums 中所有元素之和不超过 maxSumnums[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
提示：
1 <= n <= maxSum <= 1090 <= index < n运行时间: 28 ms
内存: 0.0 MB
class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
maxSum -= n # remove the contributions from all the 1 in each element.
# We will add 1 back to the final height later
if index < n // 2: # make the index closer to the right boundary
index = n - index - 1
n_left = index # number of element to the left of the index
n_right = n - 1 - index # number of element to the right of the index
tri_left = (n_left * (n_left + 1)) // 2 # the triangle area for the left side if not hitting the boundary
tri_right = (n_right * (n_right + 1)) // 2 # the triangle area for the right side if not hitting the boundary
# case 1: perfect pyramid
if maxSum <= (tri_right * 2 + n_right + 1):
return int(math.sqrt(maxSum)) + 1
# case 2: right side hits the boundary
if maxSum <= (tri_left + tri_right + (n_left - n_right) * n_right + n_left + 1):
b = 3 + 2 * n_right
return int((-b + math.sqrt(b * b - 8 * (tri_right + 1 - n_right * n_right - maxSum))) / 2) + 1 + 1
# case 3: both sides hit boundaries
maxSum -= (tri_left + tri_right + (n_left - n_right) * n_right + n_left + 1)
return n_left + 1 + 1 + (maxSum // n)
该题解利用数学方法和几何思想来求解问题。首先，它调整 index 位置，确保 index 靠近右边界，这样可以简化问题的对称性。接下来，它计算左右两侧的三角形区域的和，这些区域代表了如果中心点逐渐增加，周围元素需要按照最大差1的规则增加所需的最小总和。题解主要分为三种情况处理：1) 完美金字塔型，其中中心元素到两边的差值可以自由变化而不受边界限制；2) 右边界受限，左侧可以自由增加；3) 两侧都受到边界的限制。每种情况下，都通过数学公式来计算可能的最大中心值，同时注意到总和的限制。最后，根据计算得到的额外可用和分配给数组元素，来确定最终的最大值。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
maxSum -= n # 将所有元素初始化为1，减去这些基础值
if index < n // 2: # 如果index在左半边，则转到右半边以简化问题
index = n - index - 1
n_left = index # index左边的元素数
n_right = n - 1 - index # index右边的元素数
tri_left = (n_left * (n_left + 1)) // 2 # 左侧最大增长和，不触及边界
tri_right = (n_right * (n_right + 1)) // 2 # 右侧最大增长和，不触及边界
# 情况1：理想金字塔形
if maxSum <= (tri_right * 2 + n_right + 1):
return int(math.sqrt(maxSum)) + 1
# 情况2：右侧触及边界
if maxSum <= (tri_left + tri_right + (n_left - n_right) * n_right + n_left + 1):
b = 3 + 2 * n_right
return int((-b + math.sqrt(b * b - 8 * (tri_right + 1 - n_right * n_right - maxSum))) / 2) + 1 + 1
# 情况3：两侧都触边界
maxSum -= (tri_left + tri_right + (n_left - n_right) * n_right + n_left + 1)
return n_left + 1 + 1 + (maxSum // n)
在算法中调整index至数组的右半部是为了简化问题的对称性和计算复杂性。由于数组左右两侧的处理逻辑是对称的，如果index位于左半部，我们可以通过将其映射到右半部（即计算 `n - index - 1`），这样只需要考虑一种情况即可。这种映射使得算法的设计更为统一和简单，避免了重复编写处理左侧和右侧的代码，提高了代码的可读性和可维护性。
1) 完美金字塔型：适用条件是maxSum足够小，使得index处的值增加不会使任何一侧的元素超过边界。此时，maxSum主要用于构造以index为顶点的对称金字塔。通过求平方根来估算顶点高度，因为金字塔的总和可以近似表示为平方函数。 2) 右边界受限：适用条件是右侧元素因为边界限制而不能达到理想的金字塔形状，而左侧可以自由增加。这种情况下，需要计算左侧的自由增长和右侧达到边界时的总和，然后解一元二次方程来找到index处的最大值。 3) 两侧都受到边界的限制：当maxSum较大，两侧元素都达到边界后还有剩余的总和。此时，需要计算两侧的总和之后剩余的部分平均分配给每个元素，从而得到index处的最大可能值。
`tri_left`和`tri_right`分别代表如果中心元素逐步增加，不触及边界时，左侧和右侧可以达到的最大增长和。这两个值是通过等差数列求和公式计算得到的，表示从index向左或向右，每个元素最多可以比前一个元素多1的增长总和。在计算nums[index]的最大可能值时，这两个值帮助我们估算在不超过边界的情况下，可以向左右两侧分配的总和。如果总和超过这个值，就意味着必须考虑边界影响，或者需要重新分配多出的部分。