Daily LeetCode – day0159 1802. Maximum Value at a Given Index in a Bounded Array

// 1802. Maximum Value at a Given Index in a Bounded Array
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (valid(mid, n, index, maxSum)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }

    public boolean valid(int mid, int n, int index, int maxSum) {
        int left = index;
        int right = n - index - 1;
        long sum = mid + cal(mid, left) + cal(mid, right);
        return sum <= maxSum;
    }

    public long cal(int big, int length) {
        if (length + 1 < big) {
            int small = big - length;
            return (long) (big - 1 + small) * length / 2;
        } else {
            int ones = length - (big - 1);
            return (long) big * (big - 1) / 2 + ones;
        }
    }
}

学习笔记：
这是一道二分搜索的题目，用到的是搜索右边界的二分搜索。
然后再逐个尝试的时候，用到了贪心算法。