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

难度

• Easy
• Medium
• Hard

思路

隐含最大（ index 处的值 ）最小（总和）问题，首先考虑二分查找答案。

考虑能否在确定 index 处的值的情况下 check 其是否合乎要求。以该处值为中心，向两边依次递减 1 ，直到值为 1 ，其后若还有位置，均为 1 ，此时应当是最小总和，如果此时的总和小于最大总和，则满足条件。所以 check 的方法确定下来了，可以使用二分。

代码

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        if n == maxSum: return 1
        elif maxSum < n: return 0
        l, r = 0, maxSum
        ans = 0

        def check(x: int) -> bool:
            s1 = s2 = 0
            if index == 0:
                s1 = 0
            elif x > index:
                s1 = (x - 1 + x - index) * index // 2
            else:
                s1 = x * (x - 1) // 2
                s1 += index - x + 1
            if index == n - 1:
                s2 = 0
            elif x > n - 1 - index:
                s2 = (x - 1 + x - (n - 1 - index)) * (n - 1 - index) // 2
            else:
                s2 = x * (x - 1) // 2
                s2 += (n - 1 - index) - x + 1

            return s1 + s2 + x <= maxSum
        while l <= r:
            m = (l + r) // 2
            if check(m):
                ans = ans if ans > m else m
                l = m + 1
            else:
                r = m - 1
        return ans