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
}
评论