题目传送门

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^9

  • 0 <= index < n

2. 分析

核心思路:贪心+二分查找

题意分析:

构造一个长度为n的数组,每个元素都是正整数,相邻元素之间差值小于等于1,所有元素的元素和<=maxSum

构造满足上述条件的数组,返回数组索引为index的元素值。

由于数组的长度最大为109,我们是没办法直接进行数组模拟得到答案的。

思考:从上述条件中,我们可以抽离出什么信息?

  • 相邻元素之间差值为1,那么范围元素和求解可以利用等差公式快速求解。

  • 欲使,index尽量大,我们可以贪心index为数组最大值,两端以index降序。

  • 由于数组元素是正整数,我们得控制降序长度,不能降序到负数。

基于此,可以对index的值,作二分查找。找到满足条件的上界。

转化:

Golang 原生 sort.Search api 可以找寻条件下界,我们可以转化思路。求解 > maxSum的下界target,那么target-1 即是所求解的上界。

注意:

需要详细思考,以index为中心时,左右两端的长度划分,值划分,等差和计算及等值和计算的细节。具体参见代码。

3. 代码

func maxValue(n int, index int, maxSum int) int {
    // 二分答案+贪心
    // 分别标记以index为中心的左右两端长度
    leftn := index      // 不包含index
    rightn := n - index // 包含index
    aim := sort.Search(1e9+1, func(i int) bool {
        // i 作为index的值,要使得maxSum最小,那么index为峰值,两边需要以等差为1降序
        // 通过前n项和公式,统计值
        // 首项:i-leftn 末项:i-1 项数:leftn
        a1 := i - leftn
        var (
            leftSum  int
            rightSum int
        )
        if a1 <= 0 {
            // 不够减
            // 1,1,1,1,2,3,4...i...
            // 升序的一共有i-1个,剩下的一共有leftn-(i-1)个1
            leftSum = (1+i-1)*(i-1)/2 + (leftn - i + 1)
        } else {
            leftSum = (i - leftn + i - 1) * leftn / 2
        }
        // 首项:i 末项:i-rightn+1 项数:rightn
        end := i - rightn + 1
        if end <= 0 {
            // 不够减
            // ... i ... 4, 3, 2, 1, 1, 1, 1
            // 降序的一共有i个, 剩下的一共有rightn-i个
            rightSum = (i+1)*i/2 + (rightn - i)
        } else {
            rightSum = (i + end) * rightn / 2
        }
        return leftSum+rightSum > maxSum
    })
    return aim - 1
}