1802. 有界数组中指定下标处的最大值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 <= 10⁹
0 <= index < n

# 思路

二分

# 解法

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum; 
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (satisfy(n, index, maxSum, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    boolean satisfy(int n, int index, int maxSum, int num) {
        long sum = num; 
        int leftPart = index;
        int rightPart = n - index - 1;
        
        if (leftPart > 0) {
            if (num > leftPart) {
                sum += (long)(num - 1 + num - leftPart) * leftPart / 2;
            } else {
                sum += (long)num * (num - 1) / 2;
                sum += (leftPart - (num - 1));
            }
        }
        
        if (rightPart > 0) {
            if (num > rightPart) {
                sum += (long)(num - 1 + num - rightPart) * rightPart / 2;
            } else {
                sum += (long)num * (num - 1) / 2;
                sum += (rightPart - (num - 1));
            }
        }

        return sum <= maxSum;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# 总结

分析出几种情况，然后分别对各个情况实现

#Java