Question

1802. Maximum Value at a Given Index in a Bounded Array

中文文档

Description

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 <= n <= maxSum <= 109
• 0 <= index < n

Solutions

Solution 1: Binary Search

According to the problem description, if we determine the value of $nums[index]$ as $x$, we can find a minimum array sum. That is, the elements on the left side of $index$ in the array decrease from $x-1$ to $1$, and if there are remaining elements, the remaining elements are all $1$; similarly, the elements at $index$ and on the right side of the array decrease from $x$ to $1$, and if there are remaining elements, the remaining elements are all $1$.

In this way, we can calculate the sum of the array. If the sum is less than or equal to $maxSum$, then the current $x$ is valid. As $x$ increases, the sum of the array will also increase, so we can use the binary search method to find the maximum $x$ that meets the conditions.

To facilitate the calculation of the sum of the elements on the left and right sides of the array, we define a function $sum(x, cnt)$, which represents the sum of an array with $cnt$ elements and a maximum value of $x$. The function $sum(x, cnt)$ can be divided into two cases:

• If $x \geq cnt$, then the sum of the array is $\frac{(x + x - cnt + 1) \times cnt}{2}$
• If $x \lt cnt$, then the sum of the array is $\frac{(x + 1) \times x}{2} + cnt - x$

Next, define the left boundary of the binary search as $left = 1$, the right boundary as $right = maxSum$, and then binary search for the value $mid$ of $nums[index]$. If $sum(mid - 1, index) + sum(mid, n - index) \leq maxSum$, then the current $mid$ is valid, we can update $left$ to $mid$, otherwise we update $right$ to $mid - 1$.

Finally, return $left$ as the answer.

The time complexity is $O(\log M)$, where $M=maxSum$. The space complexity is $O(1)$.

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

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

  private long sum(long x, int cnt) {
    return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x;
  }
}

class Solution {
public:
  int maxValue(int n, int index, int maxSum) {
    auto sum = [](long x, int cnt) {
      return x >= cnt ? (x + x - cnt + 1) * cnt / 2 : (x + 1) * x / 2 + cnt - x;
    };
    int left = 1, right = maxSum;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (sum(mid - 1, index) + sum(mid, n - index) <= maxSum) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
};

func maxValue(n int, index int, maxSum int) int {
  sum := func(x, cnt int) int {
    if x >= cnt {
      return (x + x - cnt + 1) * cnt / 2
    }
    return (x+1)*x/2 + cnt - x
  }
  return sort.Search(maxSum, func(x int) bool {
    x++
    return sum(x-1, index)+sum(x, n-index) > maxSum
  })
}