中等

问题描述

给你三个正整数 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 <= 109
• 0 <= index < n

二分查找

显然 $nums[index]$ 的取值范围在 $[1, maxSum]$ 内，要使 $nums[index]$ 在数组和小于 $maxSum$ 时最大，其余值应该尽可能的小，又因为相邻两个数的差值不能大于 $1$，因此从 $index$ 开始左右两边的数递减，直到减到 $1$ 或到达数组边界，此时数组的和是固定的，因此可以二分枚举 $nums[index]$ 可能的值，使用等差数列计算公式计算 $index$ 左右两边子数组的和，最终找出最大满足数组和 $numsSum \leq maxSum$ 的 $nums[index]$。

/**
 * @param {number} n
 * @param {number} index
 * @param {number} maxSum
 * @return {number}
 */
var maxValue = function (n, index, maxSum) {
  let low = 1
  let high = maxSum
  const calc = (max, cnt) => {
    if (cnt < max) {
      return Math.floor(((max + max - cnt + 1) * cnt) / 2)
    } else {
      return Math.floor(((1 + max) * max) / 2 + cnt - max)
    }
  }
  while (low < high) {
    const mid = ~~((high + low + 1) / 2)
    const sum = mid + calc(mid - 1, index) + calc(mid - 1, n - index - 1)
    if (sum <= maxSum) {
      low = mid
    } else {
      high = mid - 1
    }
  }
  return low
}

• 时间复杂度：$O(\log(maxSum))$
• 空间复杂度：$O(1)$