题目

You are given three positive integers: n, index, and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

nums.length == n
nums[i] is a positive integer where 0 <= i < n.
abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
The sum of all the elements of nums does not exceed maxSum.
nums[index] is maximized.

Return nums[index] of the constructed array.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: n = 4, index = 2, maxSum = 6
Output: 2
Explanation: nums = [1,2,2,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2].

Example 2:

Input: n = 6, index = 1, maxSum = 10
Output: 3

Constraints:

1
2
1 <= n <= maxSum <= 109
0 <= index < n

解题思路

首先将题意转化成自己的理解

  1. 给我三个参数n, index, maxSum
  2. nums.length = n
  3. nums[i]中的元素为正整数(不要看错了)
  4. nums中相邻的两个元素的绝对值<=1
  5. sum(nums)不超过numSum
  6. nums[index]尽可能地大

想让nums[index]最大化有以下思路：

  1. 在sum(nums) <= numSum下尽可能增大nums[index]
  2. 让sum(nums)增长的尽可能缓慢

sum(nums)求和公式为：

s = index左 + nums[index] + index右 + 未被占用的元素下标(为了尽可能的小所以默认都是1)

最后我们需要二分查找(bisect)nums[index]的值

下界为1，上界为10 ** 9. 因为元素为正整数，所以下界最为1.

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def check(num) -> bool:
            # 初始化
            leftLength, leftMin = min(index - 0, num - 1), num - min(index - 0, num - 1)    # 左长度 左最小元素
            indexLeft = leftLength * leftMin + leftLength * (leftLength - 1) / 2            # 求出左边的和
            rightLength, rightMin = min(n - index - 1, num - 1), num - min(n - index - 1, num - 1)  # 右长度 右最小元素
            indexRight = rightLength * rightMin + rightLength * (rightLength - 1) / 2       # 求出右边的和
            element = 0 if (numsLeft - leftLength) + (numsRight - rightLength) < 0 else (numsLeft - leftLength) + (numsRight - rightLength)
            s = indexLeft + num + indexRight + element  # sum(nums)
            return s > maxSum

        # 初始化
        l, r = 1, 10 ** 9 + 1  # 二分上下界
        numsLeft, numsRight = index - 0, n - index - 1  # nums除去index后的左右长度
        ans = 0
        while l <= r:
            mid = (r - l >> 1) + l
            if check(mid):
                r = mid - 1
            else:
                l = mid + 1
                ans = max(ans, mid)
        return ans

C++

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
class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (valid(mid, n, index, maxSum)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    bool valid(int mid, int n, int index, int maxSum) {
        int left = index;
        int right = n - index - 1;
        return mid + cal(mid, left) + cal(mid, right) <= maxSum;
    }

    long cal(int big, int length) {
        if (length + 1 < big) {
            int small = big - length;
            return (long) (big - 1 + small) * length / 2;
        } else {
            int ones = length - (big - 1);
            return (long) big * (big - 1) / 2 + ones;
        }
    }
};

Go

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
func maxValue(n int, index int, maxSum int) int {
    numsLeft, numsRight := index - 0, n - index - 1
    check := func(num int) bool {
        leftLength, leftMin := min(index - 0, num - 1), num - min(index - 0, num - 1)
        indexLeft := leftLength * leftMin + leftLength * (leftLength - 1) / 2
        rightLength, rightMin := min(n - index - 1, num - 1), num - min(n - index - 1, num - 1)
        indexRight := rightLength * rightMin + rightLength * (rightLength - 1) / 2
        element := 0
        if numsLeft - leftLength + numsRight - rightLength > 0{
            element = numsLeft - leftLength + numsRight - rightLength
        }
        s := indexLeft + num + indexRight + element
        return s > maxSum
    }
    l, r := 1, int(math.Pow(10, 9) + 1)
    ans := 0
    for l <= r {
        mid := ((r - l) >> 1) + l
        if check(mid) {
            r = mid - 1
        } else {
            l = mid + 1
            ans = max(ans, mid)
        }
    }
    return ans
}

func max(a int, b int) int {
    if a > b {return a}
    return b
}

func min(a int, b int) int {
    if a > b {return b}
    return a
}