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

题目形容

这是 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;
    }
}

• 工夫复杂度：$O(\log{n})$
• 空间复杂度：$O(1)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.1802 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布