1.题目

给你三个正整数 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 <= n <= maxSum <= 10⁹
0 <= index < n

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array

2.思路

（1）暴力穷举法
① 用 res 来表示 nums[index]，并从 res = maxSum 开始，穷举 res，以保证 nums[index] 的值被最大化；
② 在穷举的过程中，用 sum 表示数组 nums 的所有元素之和，如果 sum <= maxSum，则说明找到了满足题目所有条件的数组 nums，此时直接返回 res 即可；否则 res–，继续下一轮穷举；
③ 当 res < 1 时，结束穷举；
需要注意的是，该方法的时间复杂度较高，为 O(mn)，所以在 LeetCode 中提交会出现“超出时间限制”的情况！

（2）贪心算法 & 二分搜索
思路参考本题官方题解。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        // 用 res 来表示 nums[index] 
        int res = maxSum;
        //从 res = maxSum 开始，枚举 res，以保证 nums[index] 的值被最大化
        while (res >= 1) {
            // sum 表示数组 nums 的所有元素之和
            long sum = res;
            //计算 nums[index + 1...0] 的和
            for (int i = index + 1; i < n; i++) {
                sum += Math.max(res - i + index, 1);
            }
            //计算 nums[0...index - 1] 的和
            for (int i = index - 1; i >= 0; i--) {
                sum += Math.max(res - index + i, 1);
            }
            //保证数组 nums 的元素之和不超过 maxSum
            if (sum <= maxSum) {
                return res;
            }
            res--;
        }
        return -1;
    }
}

//思路2————贪心算法 & 二分搜索
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int leftCnt = index;
        int rightCnt = n - index - 1;
        //二分查找的左右边界(1 <= nums[index] <= maxSum)
        int left = 1;
        int right = maxSum;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long sum = mid + calPartSum(mid, leftCnt) + calPartSum(mid, rightCnt);
            if (sum > maxSum) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }
    
    private long calPartSum(int maxNum, int cnt) {
        if (maxNum > cnt) {
            /*
                [maxNum - 1, maxNum - 2, ..., maxNum - cnt]，一共有 cnt 个数
                可直接使用等差数列的求和公式：(首项 + 尾项) * 项数 / 2  
            */
            return (long) (maxNum - 1 + maxNum - cnt) * cnt / 2;
        } else {
            /*
                maxNum <= cnt
                [maxNum - 1, maxNum - 2, ..., maxNum - cnt = 1, 1, ..., 1]，一共有 cnt 个数
                分两部分求和：[maxNum - 1, maxNum - 2, ..., 1] + [1, 1, ..., 1]，分别有 maxNum - 1 和 cnt - (maxNum - 1) 个数
            */
            return (long) (maxNum - 1 + 1) * (maxNum - 1) / 2 + cnt - (maxNum - 1);
        }
    }
}