How do I approach the "Maximum Value at a Given Index in a Bounded Array" problem?

Use binary search to find the maximum value for nums[index] that satisfies the array sum constraint. Calculate the total array sum efficiently and greedily distribute the sum around the target index.

What is the time complexity of solving the "Maximum Value at a Given Index in a Bounded Array" problem?

The time complexity is O(log(maxSum)) due to the binary search over the possible values of nums[index].

How can I ensure my array construction stays within the maxSum constraint?

By using a greedy approach to distribute the remaining sum around nums[index], and binary search to narrow down the maximum possible value for nums[index].

Can binary search always be applied to problems like this one?

Binary search is effective in problems where you're searching for an optimal value within a range, as long as the problem has a monotonic property. In this case, higher values for nums[index] lead to larger sums, making binary search appropriate.

What should I watch out for when implementing the binary search for this problem?

Make sure to properly calculate the total array sum at each binary search step, ensuring that it does not exceed maxSum. Also, be mindful of how the elements on both sides of nums[index] contribute to the sum.

#1802

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

有界数组中指定下标处的最大值

给你三个正整数 n 、 index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums （下标从 0 开始计数）： nums.length == n nums[i] 是正整数，其中 0 abs(nums[i] - nums[i+1]) ，其中 0 nums 中所有元素之和…

数学二分查找贪心

题目描述

给你三个正整数 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

lightbulb

解题思路

方法一：二分查找

根据题目描述，如果我们确定了 $nums[index]$ 的值为 $x$ ，此时我们可以找到一个最小的数组总和。也就是说，在 $index$ 左侧的数组元素从 $x-1$ 一直递减到 $1$ ，如果还有剩余的元素，那么剩余的元素都为 $1$ ；同理，在 $index$ 及右侧的数组元素从 $x$ 一直递减到 $1$ ，如果还有剩余的元素，那么剩余的元素都为 $1$ 。

这样我们就可以计算出数组的总和，如果总和小于等于 $maxSum$ ，那么此时的 $x$ 是合法的。随着 $x$ 的增大，数组的总和也会增大，因此我们可以使用二分查找的方法，找到一个最大的且符合条件的 $x$ 。

为了方便计算数组左侧、右侧的元素之和，我们定义一个函数 $sum(x, cnt)$ ，表示一共有 $cnt$ 个元素，且最大值为 $x$ 的数组的总和。函数 $sum(x, cnt)$ 可以分为两种情况：

如果 $x \geq cnt$ ，那么数组的总和为 $\frac{(x + x - cnt + 1) \times cnt}{2}$
如果 $x \lt cnt$ ，那么数组的总和为 $\frac{(x + 1) \times x}{2} + cnt - x$

接下来，定义二分的左边界 $left = 1$ ，右边界 $right = maxSum$ ，然后二分查找 $nums[index]$ 的值 $mid$ ，如果 $sum(mid - 1, index) + sum(mid, n - index) \leq maxSum$ ，那么此时的 $mid$ 是合法的，我们可以将 $left$ 更新为 $mid$ ，否则我们将 $right$ 更新为 $mid - 1$ 。

最后将 $left$ 作为答案返回即可。

时间复杂度 $O(\log M)$ ，其中 $M=maxSum$ 。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	O(\log (\text{maxSum}))
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate should identify the importance of binary search over the answer space to minimize computation time.
question_mark
Look for clear understanding of how to calculate array sums given the constraints and how to use greedy methods efficiently.
question_mark
Ensure the candidate is comfortable explaining the trade-off between maximizing nums[index] and respecting the sum constraint.

warning

常见陷阱

外企场景

error
Failing to handle edge cases, like when nums[index] is at its minimum possible value.
error
Incorrectly calculating the sum of the array for a given value of nums[index], leading to exceeding the maxSum constraint.
error
Not considering the effect of the distribution on both sides of the index when constructing the array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if maxSum is very large compared to n? The binary search will quickly converge to the maximum possible value.
arrow_right_alt
What if nums[index] is set to the minimum value? This could lead to an unbalanced array and suboptimal performance.
arrow_right_alt
What if the index is at the edge of the array (either 0 or n-1)? Special care must be taken in constructing the array around the boundary.

help

常见问题

外企场景

继续练习

#1739 放置盒子 #1648 销售价值减少的颜色球 #2358 分组的最大数量