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

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

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int l = 1, r = (int) 1e9;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (valid(mid, n, index, maxSum)) l = mid ;
            else r = mid - 1;
        }
        return l;
    }

    public boolean valid(int mid, int n, int index, int maxSum) {
        int left = index;
        int right = n - index - 1;
        return mid + cal(mid, left) + cal(mid, right) <= 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;
        }
    }
}