题目描述

给你三个正整数 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。

样例

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

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

限制

• 1 <= n <= maxSum <= 10^9
• 0 <= index < n

算法

(贪心，二分答案) $O(\log maxSum)$

1. 二分目标位置 index 的值，假设为 $m$。
2. 则需要计算在符合要求的情况下，数组能达到的整体最小值。
3. 一种最小化的构造方式类似于这样 ..., 1, 1, 1, 2, 3, ..., m-1, m, m-1, m-2, ..., 2, 1, 1, 1, ...。需要区分 idx 与 m 大小关系进行分类讨论。

时间复杂度

• 每次计算仅需要常数的时间，故总时间复杂度为 $O(\log maxSum)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
private:
    bool check(LL m, LL n, LL idx, LL maxSum) {
        LL tot = -m;
        if (m >= idx + 1) tot += (m + (m - idx)) * (idx + 1) / 2;
        else tot += (1 + m) * m / 2 + idx - m + 1;

        if (m >= n - idx) tot += (m + (m - (n - idx) + 1)) * (n - idx) / 2;
        else tot += (1 + m) * m / 2 + n - idx - m;

        return tot <= maxSum;
    }

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