难度:★★★☆☆
类型:数组
方法:数学
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给你三个正整数 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,原函数的表达式为:
根据数学的原理,我们可以计算得到这个分段函数的反函数:
在求解反函数时,中间这一段比较复杂,涉及到一元二次方程的求解公式。不过不管是一元二次方程还是等差数列求和公式,都是高中的知识,这里不再赘述。
有了上面的数学法宝,我们就可以在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解决方案,请移步力扣中等题解析
网友评论