[力扣]1802有界数组中指定下标处的最大值

今天的每日一题，纯纯数学题啊！可惜我算了半天，最后自己写的算法超时了。事后看了看官方的解决方案，发现我就差一点了，我是最大值从1逐渐递增，而官方是从maSum往下递减，然后采用了对分查找减少次数。这次题解就直接用官方的好了。

题目

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

难度：中等

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

思路

方法一：贪心 + 二分查找

思路

根据题意，需要构造一个长度为 n 的数组 $\textit{nums}$，所有元素均为正整数，元素之和不超过 $\textit{maxSum}$，相邻元素之差不超过 11，且需要最大化 $\textit{nums}[\textit{index}]$。根据贪心的思想，可以使$\textit{nums}[\textit{index}]$成为数组最大的元素，并使其他元素尽可能小，即从$\textit{nums}[\textit{index}]$开始，往左和往右，下标每相差 11，元素值就减少 11，直到到达数组边界，或者减少到仅为 11 后保持为 11 不变。

根据这个思路，一旦 $\textit{nums}[\textit{index}]$ 确定后，这个数组的和 $\textit{numsSum}$也就确定了。并且 $\textit{nums}[\textit{index}]$ 越大，数组和 $\textit{numsSum}$ 也越大。据此，可以使用二分搜索来找出最大的使得 $\textit{numsSum} \leq \textit{maxSum}$成立的$\textit{nums}[\textit{index}]$。

代码实现上，二分搜索的左边界为 11，右边界为 $\textit{maxSum}$。函数 $\textit{valid}$ 用来判断当前的 $\textit{nums}[\textit{index}]$对应的 $\textit{numsSum}$ 是否满足条件。$\textit{numsSum}$ 由三部分组成，$\textit{nums}[\textit{index}]$，$\textit{nums}[\textit{index}]$ 左边的部分之和，和 $\textit{nums}[\textit{index}]$ 右边的部分之和。$\textit{cal}$ 用来计算单边的元素和，需要考虑边界元素是否早已下降到 11 的情况。

复杂度分析

时间复杂度：$O(\lg (\textit{maxSum}))$。二分搜索上下界的差为$\textit{maxSum}$。

空间复杂度：$O(1)$，仅需要常数空间。

方法二：数学推导

思路

仍然按照方法一的贪心思路，根据方法一的推导，$\textit{nums}[\textit{index}]$ 左边或者右边的元素和，要分情况讨论。记 $\textit{nums}[\textit{index}]$ 为$\text{big}$，它离数组的某个边界的距离为 $\textit{length}$。当$\text{big} \leq \textit{length+1}$时，还未到达边界附近时，元素值就已经降为 11，并保持为 11 直到到达数组边界，此时这部分的元素和为 $\dfrac{\textit{big}^2-3\textit{big}}{2}+\textit{length}+1$ 。否则，元素会呈现出梯形的形状，此时这部分的元素和为$\dfrac{(2\textit{big}-\textit{length}-1)\times\textit{length}}{2}$ 。$\textit{numsSum}$由三部分组成，$\textit{nums}[\textit{index}]$，$\textit{nums}[\textit{index}]$ 左边的部分之和，和 $\textit{nums}[\textit{index}]$ 右边的部分之和。记 $\textit{nums}[\textit{index}]$ 左边的元素个数为 $\textit{left}= \textit{index}$，右边的元素个数为 $\textit{right} = n-1-\textit{index}$。根据对称性，不妨设 $\textit{left} \leq \textit{right}$。这样一来，$\textit{numsSum}$的组成可以用三种情况来表示。即:

• $\textit{big} \leq \textit{left+1}big≤left+1，\textit{numsSum} = \dfrac{\textit{big}^2-3\textit{big}}{2}+\textit{left}+1 + \textit{big} + \dfrac{\textit{big}^2-3\textit{big}}{2}+\textit{right}+1$

• $\textit{left+1} \lt \textit{big} \leq \textit{right+1}left+1<big≤right+1, \textit{numsSum} = \dfrac{(2\textit{big}-\textit{left}-1)\times\textit{left}}{2} + \textit{big} + \dfrac{\textit{big}^2-3\textit{big}}{2}+\textit{right}+1$

• $\textit{right+1} \lt \textit{big}right+1<big, \textit{numsSum} = \dfrac{(2\textit{big}-\textit{left}-1)\times\textit{left}}{2} + \textit{big} + \dfrac{(2\textit{big}-\textit{right}-1)\times\textit{right}}{2}$
  ​

对于前两种情况，我们可以分别求出上限，如果上限不超过$\textit{maxSum}$，则可以通过解一元二次方程来求出$\textit{big}$。否则需要根据第三种情况解一元一次方程来求$\textit{big}$。

复杂度分析

• 时间复杂度：$O(1)$，仅使用常数时间。

• 空间复杂度：$O(1)$，仅使用常数空间。

代码

思路一

func f(big, length int) int {
    if length == 0 {
        return 0
    }
    if length <= big {
        return (2*big + 1 - length) * length / 2
    }
    return (big+1)*big/2 + length - big
}

func maxValue(n, index, maxSum int) int {
    return sort.Search(maxSum, func(mid int) bool {
        left := index
        right := n - index - 1
        return mid+f(mid, left)+f(mid, right) >= maxSum
    })
}

思路二

func maxValue(n, index, maxSum int) int {
    left := index
    right := n - index - 1
    if left > right {
        left, right = right, left
    }

    upper := ((left+1)*(left+1)-3*(left+1))/2 + left + 1 + (left + 1) + ((left+1)*(left+1)-3*(left+1))/2 + right + 1
    if upper >= maxSum {
        a := 1.0
        b := -2.0
        c := float64(left + right + 2 - maxSum)
        return int((-b + math.Sqrt(b*b-4*a*c)) / (2 * a))
    }

    upper = (2*(right+1)-left-1)*left/2 + (right + 1) + ((right+1)*(right+1)-3*(right+1))/2 + right + 1
    if upper >= maxSum {
        a := 1.0 / 2
        b := float64(left) + 1 - 3.0/2
        c := float64(right + 1 + (-left-1)*left/2.0 - maxSum)
        return int((-b + math.Sqrt(b*b-4*a*c)) / (2 * a))
    } else {
        a := float64(left + right + 1)
        b := float64(-left*left-left-right*right-right)/2 - float64(maxSum)
        return int(-b / a)
    }
}