前言：
今天姐妹们对“java输出数组最大值和下标”可能比较关心，小伙伴们都想要剖析一些“java输出数组最大值和下标”的相关资讯。那么小编也在网摘上搜集了一些有关“java输出数组最大值和下标””的相关内容，希望姐妹们能喜欢，我们一起来学习一下吧！题目
给你三个正整数 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
解题思路分析
1、二分查找；时间复杂度O(log(n))，空间复杂度O(1)
func maxValue(n int, index int, maxSum int) int { if n == 1 { return maxSum } res := 1 leftTotal, rightTotal := index, n-index-1 left, right := 1, maxSum for left < right { mid := left + (right-left)/2 l := getTotal(mid, leftTotal) r := getTotal(mid, rightTotal) if l+r+mid <= maxSum { left = mid + 1 res = mid } else { right = mid } } return res}func getTotal(high int, total int) int { need := high - 1 if need >= total { return total * (need + high - total) / 2 } return need*(1+need)/2 + total - need}2、二分查找；时间复杂度O(log(n))，空间复杂度O(1)
func maxValue(n int, index int, maxSum int) int { res := 1 leftTotal, rightTotal := index, n-index-1 left, right := 1, maxSum+1 for left < right { mid := left + (right-left)/2 l := getTotal(mid, leftTotal) r := getTotal(mid, rightTotal) if l+r+mid <= maxSum { left = mid + 1 res = mid } else { right = mid } } return res}func getTotal(high int, total int) int { need := high - 1 if need >= total { return total * (need + high - total) / 2 } return need*(1+need)/2 + total - need}总结Medium题目，采用贪心思想计算可以构造的数组，采用二分查找的方式计算可以达到的nums[index] 的最大值
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #java输出数组最大值和下标
