关于后端:面试高频题难度-35综合构造题

0次阅读

共计 1761 个字符，预计需要花费 5 分钟才能阅读完成。

这是 LeetCode 上的 1802. 有界数组中指定下标处的最大值 ，难度为中等。

Tag :「二分」、「数学」、「结构」、「贪婪」、「模仿」

给你三个正整数 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^9$
$0 <= index < n$

依据题意，容易想到以 ans 为宰割点的正整数数组具备二段性，其中 ans 为最大的 $nums[idx]$。

小于等于 ans 的值均能通过间接调整 $nums[idx]$ 来结构，不会违反总和不超过 max 的限度；大于 ans 的值则无奈满足 max 限度。基于此咱们可通过「二分」的形式来找宰割点。

假如以后二分到的值为 x，思考如何实现一个 check 函数，该函数用于判断 x 是否作为 $nums[idx]$：

为了令 $nums[idx] = x$ 时，数组总和 sum 不超过 max 限度，咱们该当贪婪结构 $nums$ 的残余元素：从 $idx$ 开始往两侧结构，依照递加的形式进行一一结构，若递加到 $1$ 则维持不变。

这样可确保结构进去的 $nums$ 既满足 $nums[idx] = x$ 同时元素总和最小。

地位 idx 的值为 x，其右边有 idx 个元素，其左边有 n - idx - 1 个元素。

利用「等差数列求和」公式别离从 x - 1 开始结构（留神：这里说的结构仅是计算 $nums$ 总和），若总和不超过 max 阐明 $nums[idx] = x$ 满足要求，咱们令 $l = mid$，否则令 $r = mid – 1$。

代码：

class Solution {public int maxValue(int n, int index, int max) {
        long l = 1, r = max;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (check(n, mid, index, max)) l = mid;
            else r = mid - 1;
        }
        return (int) r;
    }
    boolean check(int n, long x, int idx, int max) {
        long sum = x;
        if (idx > x - 1) {
            long an = x - 1, a1 = 1, cnt = x - 1;
            sum += cnt * (a1 + an) / 2;
            sum += idx - cnt;
        } else {
            long cnt = idx, an = x - 1, a1 = an - cnt + 1;
            sum += cnt * (a1 + an) / 2;
        }
        if (n - idx - 1 > x - 1) {
            long an = x - 1, a1 = 1, cnt = x - 1;
            sum += cnt * (a1 + an) / 2;
            sum += n - idx - 1 - cnt;
        } else {
            long cnt = n - idx - 1, an = x - 1, a1 = an - cnt + 1;
            sum += cnt * (a1 + an) / 2;
        }
        return sum <= max;
    }
}