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

题目

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 <= n <= maxSum <= 10^9
• 0 <= index < n

题解

方法一：

思路

要让nums[index]最大化，然后nums的总和最小，可以贪心地让数组形成以index最大然后向两侧逐渐递减，注意每个值最低不小于1。
假设f(x)是当nums[index] = x时的nums总和。显然f(x)单调递增，我们可以用二分法找到最后一个满足f(x)<=maxSum的x。

代码

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        auto calc = [&](long x) {
            long l = x-index, r = x-n+1L+index;
            long rt = -x;
            if (l>0) {
                rt += (l+x)*(index+1)/2;
            } else {
                rt += (1+x)*x/2+1-l;
            }
            if (r>0) {
                rt += (r+x)*(n-index)/2;
            } else {
                rt += (1+x)*x/2+1-r;
            }
            return rt;
        };
        long l = 0, r = maxSum+1;
        while (l<r) {
            long m = l+r>>1;
            if (calc(m)<=maxSum) l = m+1;
            else r = m;
        }
        return r-1;
    }
};