题目传送门

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的元素值。

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

思考：从上述条件中，我们可以抽离出什么信息？

• 相邻元素之间差值为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
}