【2023-01-04每日一题】1802. 有界数组中指定下标处的最大值[Medium]

2023-01-04
1分钟阅读时长

2023-01-04每日一题:1802. 有界数组中指定下标处的最大值

难度:Medium

标签:贪心 、 二分查找

给你三个正整数 nindexmaxSum 。你需要构造一个同时满足下述所有条件的数组 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

方法一:

详细思路过程见官方题解,这里只做个人刷题记录,方便后续查询阅读

func maxValue(n int, index int, maxSum int) int {

}

复杂度分析

LeetCode题库地址