leetcode 1802. 有界数组中指定下标处的最大值-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 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

提示：

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

思路，采用二分法，每次设定一个最大值，然后缩小范围就可以计算出结果文章来源地址https://www.toymoban.com/news/detail-572325.html

class Solution:

    ## 从 x-1 开始逐渐变小的 n 个数相加
    def  curSum(self, x, n):
        if x-n >=1:
            return int((n*(2*x-n-1))/2)
        else:
            return int(x*(x-1)/2) + n - x + 1

    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        ##index 在中间略靠右一点
        left, right = 1, maxSum
        while left < right:
            mid = int((left + right+1)/2)
            leftSum = self.curSum(mid, index)
            rightSum = self.curSum(mid, n-1-index)
            sum = leftSum + rightSum + mid
            if sum == maxSum:
                return mid
            elif sum > maxSum:
                right = mid-1
            else:
                left = mid
        return left