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

题目链接

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：

• nums.length == n
• nums[i] 是 正整数 ，其中 0 <= i < n
• abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
• nums 中所有元素之和不超过 maxSum
• nums[index] 的值被最大化

返回你所构造的数组中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

示例 1：

输入：n = 4, index = 2,  maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

示例 2：

输入：n = 6, index = 1,  maxSum = 10
输出：3

一开始以为是找规律，还打表找了半天的规律，后来转念一想发现这不就是二分吗，我们只需要二分那个最大值，从它的下标往两边值递减即可，注意值最小是 1，另外对数列求和会爆 int，所以二分判断到时候要用 longlong，AC 代码如下：

class Solution {
public:
    bool check(long long x, long long y, long long z, long long n) {
        long long num1 = y, num2 = n - y - 1;
        long long sum1 = 0, sum2 = 0;
        if (num1 >= x - 1) {
            sum1 = (x - 1) * x / 2 + num1 - (x - 1);
        } else {
            sum1 = num1 * (x - num1 + x - 1) / 2;
        }
        if (num2 >= x - 1) {
            sum2 = (x - 1) * x / 2 + num2 - (x - 1);
        } else {
            sum2 = num2 * (x - num2 + x - 1) / 2;
        }
        return (sum1 + sum2 + x <= z);
    }

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