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 <= 109 -
0 <= index < n
Solution
上个月在leetcode评论区看到一句话：最大值最小或者最小值最大可以视为二分的代名词。
所以看到题目就一眼二分了。具体来说，肯定是一个nums[index]最大，然后两边依次以1递减的这么个形状。
然后在审题上被摆了一道：nums中的所有元素都需要是正整数。而不能减小到0.
代码(Rust)
impl Solution {
pub fn max_value(n: i32, index: i32, max_sum: i32) -> i32 {
let mut l: i64 = 1;
let mut n = n as i64;
let mut index = index as i64;
let mut max_sum = max_sum as i64;
let mut r: i64 = 1_000_000_001; // [l, r)
while l < r{
let mid: i64 = (l + r)/2;
let cur: i64 = if index + 1 >= mid {
(mid + 1)*mid / 2 + index + 1 - mid
}else{
let tmp: i64 = mid - index - 1;
(mid + 1)*mid / 2 - (tmp + 1) * tmp / 2
} + if n - index >= mid{
(mid + 1)*mid / 2 + n - index - mid
}else{
let tmp: i64 = mid - n + index;
(mid + 1)*mid / 2 - (tmp + 1) * tmp / 2
} - mid;
if cur > max_sum{
r = mid; // mid cannot satisfy.
}else{
l = mid + 1; // mid can satisfy.
}
}
(l - 1) as i32
}
}