题目形容
这是 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 多平台公布