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

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        lo, hi, ans = 1, maxSum - n + 1, 1
        while lo <= hi:
            mid = (lo + hi) // 2
            s = 0
            # 计算0..index构成的等差序列和，index的值为mid，向左依次递减
            if mid > index:  # 从第0项开始，能构成等差序列，用等差序列求和公式计算0..index的和
                s = (index + 1) * (mid - index + mid) // 2
            else:  # 数组最左边（有index + 1 - mid个）都是1，剩余的mid个元素才是等差序列
                s = mid * (1 + mid) // 2 + index + 1 - mid
            # 计算index+1..n-1的等差序列和，index右边第1个元素是mid-1，逻辑与上面类似
            rightSize = n - index - 1
            if mid > rightSize:
                s += rightSize * (mid - 1 + mid - 1 - (rightSize - 1)) // 2
            else:
                s += (mid - 1) * (1 + mid - 1) // 2 + rightSize - (mid - 1)
            if s > maxSum:
                hi = mid - 1
            else:
                ans = mid
                lo = mid + 1
        return ans