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 <= 10^9
• 0 <= index < n

---

解题分析及思路：

方法：贪心+二分查找+数学

• 采用贪心的方法，假设下标为index处的值最大，那么从index处往两边扩散，为依次递减，直至减到1后一直为零，这是满足题意的最佳情况。

• 结合二分查找的方法，下标为index处的最终值的大小一定在范围[1,maxSum]内，那么可以采用二分查找的方法找到该值，判断条件为index处的值 + index处左边所有元素 + index处右边所有元素 之和是否小于maxSum

• 采用数学的方法，计算index处左边所有元素和index处右边所有元素的和，可以采用等差数列求和的方法，计算index处左边所有元素和index处右边所有元素的和。

  针对某一边而言：

  • 当index处的值小于等于该边的长度时，可以采用等差数列求和的方法计算，其公式为(2*max + 1 - length) * length / 2
  • 当index处的值大于该边的长度时，可以采用等差数列求和的方法计算，其公式为(max+1)*max/2 + length - max

  另一边同理。

func maxValue(n, index, maxSum int) int {
	var left, right = 1, maxSum
	for left < right {
		mid := left + (right-left)>>1
		if mid+cal(mid, index)+cal(mid, n-index-1) < maxSum {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

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

复杂度：

• 时间复杂度：O(logN)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:1.9 MB,击败了100.00% 的Go用户