跳到主要内容

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

· 阅读需 3 分钟

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 <= 109
  • 0 <= index < n

2、思路​

跟官解思路一贪心+二分查找相似，从均值 Math.ceil(maxSum / n) 开始枚举最大元素 nums[index]，然后按照贪心思路计算左右两边元素，其左右两边的元素是公差为 1 的递减的等差数列，递减到 1 之后其他元素都为 1，最后返回使得整个数组之和小于等于 maxSum 的最大 nums[index]。

3、代码​

function maxValue(n: number, index: number, maxSum: number): number {
    function sumNums(ak: number, k: number) {
        let sum = 0;
        const a0 = ak - (k - 1);
        
        if (k > 0) {
            if (a0 >= 1) sum += (a0 + ak) * k / 2;
            else {
                sum += (1 + ak) * ak / 2 + (k - ak);
            }
        }

        return sum;
    }

    function search(max: number) {
        let sum = -max;

        // sum:0 ~ index
        sum += sumNums(max, index + 1);

        // sum:index ~ n-1
        sum += sumNums(max, n - index);

        return sum <= maxSum;
    }

    const avg = Math.ceil(maxSum / n);
    for (let c = 0; c > -1; c++) {
        const valid = search(avg + c);
        if (!valid) return avg + c - 1;
    }
};

4、执行结果​

image.png