难度：★★★☆☆
类型：数组
方法：数学

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

提示：

1 <= n <= maxSum <= 109
0 <= index < n

解答

方案1：二分法

题目的要求是，希望我们在构建长度为n的数组时尽可能最大化index位置处的元素，并且限制了数组元素和maxSum以及相邻元素的最大梯度为1。

很容易发现，为了满足maxSum条件下最大化index位置处元素，我们应该让数组在index位置处尽可能尖锐，而梯度的限制决定了该位置处的值会影响相邻位置处的值，进而影响整个数组的排布。如果把数组各个位置画一条折线图，就会发现我们希望的结果是呈现一个倒直角三角形的形态。

我们定义一个函数f，函数的自变量x代表了index处的数值，函数的返回值代表了在index是x的情况下，整个数组的和。很容易发现，f(x)随着x的增加是单调递增的，题目实际上是给出了一个因变量的范围，让我们求取最大的x，对于这一类单调函数求自变量的问题，常常可以使用二分法解决。

定义一个函数check，函数的输入为x，函数的输出为布尔量，代表index位置处填写x，并且满足梯度约束的情况下，对应的数组和f(x)能否满足最大和maxSum的限制。其实f(x)是一个分段函数，根据index左侧元素的个数left和右侧元素的个数right，可以计算两者当中的最小值x1与最大值x2，函数在x1和x2两个分界点处分段。根据输入x与x1和x2之间的数值关系可以判断函数应该属于哪一段，进而使用该段内的函数表达式，每一段的函数表达式常常会用到等差数列求和公式得到，详细公式不再赘述。

有了判别函数check，就可以使用二分法，二分法搜索的上下界可以设定为0和maxSum，使用通用二分搜索代码即可实现。这里需要注意一下最终结果的处理。

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:

        left, right = index, n - 1 - index
        x1, x2 = min(left, right), max(left, right)

        def check(x):
            if x <= x1:
                s = (x - 1) ** 2 + n
            elif x <= x2:
                s = x + (((x - 1) + (x - x1)) * x1) // 2 + (((x - 1) + 1) * (x - 1)) // 2 + (x2 - (x - 1))
            else:
                s = x + (((x - 1) + (x - x1)) * x1) // 2 + (((x - 1) + (x - x2)) * x2) // 2
            return s <= maxSum

        left, right = 1, maxSum

        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid

        return left if check(left) else left - 1


s = Solution()
print(s.maxValue(1, 0, 24))
print(s.maxValue(3, 2, 18))
print(s.maxValue(4, 0, 4))
print(s.maxValue(4, 2, 6))
print(s.maxValue(6, 1, 10))

方案2：数学

由于上述分段函数的公式我们可以严格得知，因此求出其反函数，即可通过反函数得到自变量的取值。

为了便于读者理解，我们将题目稍作修改，最小值设置为零而不是1，这里举个例子，设n=11，index=7的情况。那么对于不同x，增量increment和当前和f(x)会是这样：

"""
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
left = 7, right = 3, x1 = 3, x2 = 7

x                array              increment   f(x)
0   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   0       0
1   [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]   1       1
2   [0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0]   3       1 + 3 = 4
3   [0, 0, 0, 0, 0, 1, 2, 3, 2, 1, 0]   5       1 + 3 + 5 = 9

4   [0, 0, 0, 0, 1, 2, 3, 4, 3, 2, 1]   7       9 + 7 = 16
5   [0, 0, 0, 1, 2, 3, 4, 5, 4, 3, 2]   8       9 + 7 + 8 = 24
6   [0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3]   9       9 + 7 + 8 + 9 = 33
7   [0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4]   10      9 + 7 + 8 + 9 + 10 = 43

8   [1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5]   11      43 + 11 = 54
9   [2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6]   11      43 + 11 + 11 = 65
...
"""

我们看到，在不同的分段内，增量是逐渐减小的，且变化的数值在三段内分别是2,1和0。设x1和x2处的函数值分别是f1和f2，原函数的表达式为：

$f\left ( x\right )=\left\{\begin{matrix} x^2 & 0 \leqslant x \leqslant x_1 & \\ f\left ( x_1\right )+\frac{\left ( \left ( 2x_1+1\right ) + \left ( 2x_1+x-x_1\right ) \right )\times \left ( x-x_1\right )}{2} & x_1 < x \leqslant x_2 & \\ f\left ( x_2\right ) + \left ( x-x2\right )\times n& x > x_2 & \end{matrix}\right.$

根据数学的原理，我们可以计算得到这个分段函数的反函数：

$f^{-1}\left ( y\right )=\left\{\begin{matrix} \sqrt{y} & 0 \leqslant y \leqslant f\left ( x_1\right ) & \\ f\left ( x_1\right )+\left \lfloor \frac{-\left ( 4x_1+1\right )+\sqrt{\left ( 4x_1+1\right )^2+8\left ( y-f\left ( x_1\right )\right )}}{2}\right \rfloor + x_1 & f\left ( x_1\right ) < y \leqslant f\left ( x_2\right ) & \\ \left \lfloor \frac{ y-f\left ( x_2\right )}{n}\right \rfloor & y> f\left ( x_2\right ) & \\ \end{matrix}\right.$

在求解反函数时，中间这一段比较复杂，涉及到一元二次方程的求解公式。不过不管是一元二次方程还是等差数列求和公式，都是高中的知识，这里不再赘述。

有了上面的数学法宝，我们就可以在O(1)的时间复杂度和O(1)的空间复杂度内快速得到结果。

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:

        left, right = index, n - 1 - index
        x1, x2 = min(left, right), max(left, right)

        f1 = x1 ** 2
        f2 = f1 + ((2 * x1 + 1) + (2 * x1 + (x2 - x1))) * (x2 - x1) // 2

        if maxSum <= f1:
            return int(maxSum ** 0.5)
        if maxSum <= f2:
            return int((- (4 * x1 + 1) + ((4 * x1 + 1) ** 2 + 8 * (maxSum - f1)) ** 0.5) / 2) + x1
        return int((maxSum - f2) / n) + x2

这里还需要注意的是，我们的函数允许数组中出现0，但是题目中要求数组中所有元素最少也是1，因此需要针对这个问题处理一下，不过处理过程非常简单。

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:

        left, right = index, n - 1 - index
        x1, x2 = min(left, right), max(left, right)

        f1 = x1 ** 2
        f2 = f1 + ((2 * x1 + 1) + (2 * x1 + (x2 - x1))) * (x2 - x1) // 2

        maxSum -= n

        if maxSum <= f1:
            res = int(maxSum ** 0.5)
        elif maxSum <= f2:
            res = int((- (4 * x1 + 1) + ((4 * x1 + 1) ** 2 + 8 * (maxSum - f1)) ** 0.5) / 2) + x1
        else:
            res = int((maxSum - f2) / n) + x2
        return res + 1


s = Solution()
print(s.maxValue(4, 0, 4))
print(s.maxValue(4, 2, 6))
print(s.maxValue(6, 1, 10))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析

1802. 有界数组中指定下标处的最大值（Python）

1802. 有界数组中指定下标处的最大值（Python）

题目

解答

方案1：二分法

方案2：数学