class Solution {
public:
int maxValue(int n, int index, int maxSum) {
}
};
1802. 有界数组中指定下标处的最大值
给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：
nums.length == nnums[i] 是 正整数 ，其中 0 <= i < nabs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1nums 中所有元素之和不超过 maxSumnums[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 <= 1090 <= index < n原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2023-01-04 10:18:57
class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
def sum(x, cnt):
return (x + x - cnt + 1) * cnt // 2 if x >= cnt else (x + 1) * x // 2 + cnt - x
left, right = 1, maxSum
while left < right:
mid = (left + right + 1) >> 1
if sum(mid - 1, index) + sum(mid, n - index) <= maxSum:
left = mid
else:
right = mid - 1
return left
python3 解法, 执行用时: 48 ms, 内存消耗: 15 MB, 提交时间: 2023-01-04 10:18:30
class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
l, r = -1, maxSum + 1
maxSum -= n # 第一层
while l + 1 < r:
m = l + r >> 1
x,y = m - index - 1,m - n + index
s, s1, s2 = m ** 2, max(0,x)*(x+1)//2, max(0,y)*(y+1)//2
if s - s1 - s2 <= maxSum:
l = m
else:
r = m
return l + 1
golang 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2023-01-04 10:16:21
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)
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2023-01-04 10:16:06
class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
left = index
right = n - index - 1
if left > right:
left, right = right, left
upper = ((left + 1) ** 2 - 3 * (left + 1)) // 2 + left + 1 + (left + 1) + ((left + 1) ** 2 - 3 * (left + 1)) // 2 + right + 1
if upper >= maxSum:
a = 1
b = -2
c = left + right + 2 - maxSum
return floor(((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a)))
upper = (2 * (right + 1) - left - 1) * left // 2 + (right + 1) + ((right + 1) ** 2 - 3 * (right + 1)) // 2 + right + 1
if upper >= maxSum:
a = 1/2
b = left + 1 - 3/2
c = right + 1 + (-left - 1) * left / 2 - maxSum
return floor(((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a)))
else:
a = left + right + 1
b = (-left ** 2 - left - right ** 2 - right) / 2 - maxSum
return floor(-b / a)
javascript 解法, 执行用时: 60 ms, 内存消耗: 41.6 MB, 提交时间: 2023-01-04 10:15:25
/**
* @param {number} n
* @param {number} index
* @param {number} maxSum
* @return {number}
*/
var maxValue = function(n, index, maxSum) {
let left = 1, right = maxSum;
while (left < right) {
const mid = Math.floor((left + right + 1) / 2);
if (valid(mid, n, index, maxSum)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
const valid = (mid, n, index, maxSum) => {
let left = index;
let right = n - index - 1;
return mid + cal(mid, left) + cal(mid, right) <= maxSum;
}
const cal = (big, length) => {
if (length + 1 < big) {
const small = big - length;
return Math.floor((big - 1 + small) * length / 2);
} else {
const ones = length - (big - 1);
return Math.floor(big * (big - 1) / 2) + ones;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-01-04 10:15:01
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
})
}
python3 解法, 执行用时: 48 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-04 10:14:25
# 贪心 + 二分查找
class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
left, right = 1, maxSum
while left < right:
mid = (left + right + 1) // 2
if self.valid(mid, n, index, maxSum):
left = mid
else:
right = mid - 1
return left
def valid(self, mid: int, n: int, index: int, maxSum: int) -> bool:
left = index
right = n - index - 1
return mid + self.cal(mid, left) + self.cal(mid, right) <= maxSum
def cal(self, big: int, length: int) -> int:
if length + 1 < big:
small = big - length
return ((big - 1 + small) * length) // 2
else:
ones = length - (big - 1)
return (big - 1 + 1) * (big - 1) // 2 + ones