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 <= 10⁹
0 <= index < n

解法

方法一：二分查找

根据题目描述，如果我们确定了 \(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)\)。

Python3JavaC++Go

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
    })
}

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

题目描述

解法

方法一：二分查找

评论