1802. 有界数组中指定下标处的最大值【贪心 +二分】

分析

我们通过二分最大值来看
函数是啥？
就是最大值val固定后，可以最贪心得最小maxSum
分两种情况考虑，如果长度比val得值要大，最贪心得就是1111.23. val
其次如果要小最贪新得就是val - length + 1 … val
计算前后之和减去重复得val就是当前得最小maxSum

ac code

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        # constructive
        # nums[index]越大,maxSum越大

        # greedy get min sum
        def check(val, length):
            if length >= val:
                # 111..23..val
                return (1 + val) * val // 2 + length - val
            else:
                # val - length + 1 -> val
                return (2 * val - length + 1) * length // 2
        
        l, r = 1, maxSum
        while l + 1 < r:
            #print(l, r)
            mid = (l + r) // 2
            if check(mid, index + 1) + check(mid, n - index) - mid > maxSum:
                r = mid - 1
            else:
                l = mid
        
        for ans in range(r, l - 1, -1):
            if check(ans, index + 1) + check(ans, n - index) - ans <= maxSum:
                return ans

总结

单调性：maxn越大，maxSum越大（贪心找最小）
等差数列公式