|
| 1 | +### 题目描述 |
| 2 | + |
| 3 | +这是 LeetCode 上的 **[1802. 有界数组中指定下标处的最大值](https://acoier.com/2023/01/06/1802.%20%E6%9C%89%E7%95%8C%E6%95%B0%E7%BB%84%E4%B8%AD%E6%8C%87%E5%AE%9A%E4%B8%8B%E6%A0%87%E5%A4%84%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC%EF%BC%88%E4%B8%AD%E7%AD%89%EF%BC%89/)** ,难度为 **中等**。 |
| 4 | + |
| 5 | +Tag : 「二分」、「数学」、「构造」、「贪心」、「模拟」 |
| 6 | + |
| 7 | + |
| 8 | + |
| 9 | +给你三个正整数 `n`、`index` 和 `maxSum`。你需要构造一个同时满足下述所有条件的数组 `nums`(下标 从 `0` 开始 计数): |
| 10 | + |
| 11 | +* `nums.length == n` |
| 12 | +* `nums[i]` 是 正整数 ,其中 `0 <= i < n` |
| 13 | +* `abs(nums[i] - nums[i+1]) <= 1` ,其中 `0 <= i < n-1` |
| 14 | +* `nums` 中所有元素之和不超过 `maxSum` |
| 15 | +* `nums[index]` 的值被 最大化 |
| 16 | +* 返回你所构造的数组中的 `nums[index]` |
| 17 | + |
| 18 | +注意:`abs(x)` 等于 `x` 的前提是 `x >= 0`;否则,`abs(x)` 等于 `-x`。 |
| 19 | + |
| 20 | +示例 1: |
| 21 | +``` |
| 22 | +输入:n = 4, index = 2, maxSum = 6 |
| 23 | + |
| 24 | +输出:2 |
| 25 | + |
| 26 | +解释:数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。 |
| 27 | +``` |
| 28 | +示例 2: |
| 29 | +``` |
| 30 | +输入:n = 6, index = 1, maxSum = 10 |
| 31 | + |
| 32 | +输出:3 |
| 33 | +``` |
| 34 | + |
| 35 | +提示: |
| 36 | +* 1ドル <= n <= maxSum <= 10^9$ |
| 37 | +* 0ドル <= index < n$ |
| 38 | + |
| 39 | +--- |
| 40 | + |
| 41 | +### 二分 + 贪心 + 数学 |
| 42 | + |
| 43 | +根据题意,容易想到以 `ans` 为分割点的正整数数组具有二段性,其中 `ans` 为最大的 $nums[idx]$。 |
| 44 | + |
| 45 | +小于等于 `ans` 的值均能通过直接调整 $nums[idx]$ 来构造,不会违反总和不超过 `max` 的限制;大于 `ans` 的值则无法满足 `max` 限制。基于此我们可通过「二分」的方式来找分割点。 |
| 46 | + |
| 47 | +假设当前二分到的值为 `x`,考虑如何实现一个 `check` 函数,该函数用于判断 `x` 能否作为 $nums[idx]$: |
| 48 | + |
| 49 | +为了令 $nums[idx] = x$ 时,数组总和 `sum` 不超过 `max` 限制,我们应当贪心构造 $nums$ 的剩余元素:从 $idx$ 开始往两侧构造,按照递减的方式进行逐个构造,若递减到 1ドル$ 则维持不变。 |
| 50 | + |
| 51 | +这样可确保构造出来的 $nums$ 既满足 $nums[idx] = x$ 同时元素总和最小。 |
| 52 | + |
| 53 | + |
| 54 | + |
| 55 | +位置 `idx` 的值为 `x`,其左边有 `idx` 个元素,其右边有 `n - idx - 1` 个元素。 |
| 56 | + |
| 57 | +利用「等差数列求和」公式分别从 `x - 1` 开始构造(注意:这里说的构造仅是计算 $nums$ 总和),若总和不超过 `max` 说明 $nums[idx] = x$ 满足要求,我们令 $l = mid,ドル否则令 $r = mid - 1$。 |
| 58 | + |
| 59 | +代码: |
| 60 | +```Java |
| 61 | +class Solution { |
| 62 | + public int maxValue(int n, int index, int max) { |
| 63 | + long l = 1, r = max; |
| 64 | + while (l < r) { |
| 65 | + long mid = l + r + 1 >> 1; |
| 66 | + if (check(n, mid, index, max)) l = mid; |
| 67 | + else r = mid - 1; |
| 68 | + } |
| 69 | + return (int) r; |
| 70 | + } |
| 71 | + boolean check(int n, long x, int idx, int max) { |
| 72 | + long sum = x; |
| 73 | + if (idx > x - 1) { |
| 74 | + long an = x - 1, a1 = 1, cnt = x - 1; |
| 75 | + sum += cnt * (a1 + an) / 2; |
| 76 | + sum += idx - cnt; |
| 77 | + } else { |
| 78 | + long cnt = idx, an = x - 1, a1 = an - cnt + 1; |
| 79 | + sum += cnt * (a1 + an) / 2; |
| 80 | + } |
| 81 | + if (n - idx - 1 > x - 1) { |
| 82 | + long an = x - 1, a1 = 1, cnt = x - 1; |
| 83 | + sum += cnt * (a1 + an) / 2; |
| 84 | + sum += n - idx - 1 - cnt; |
| 85 | + } else { |
| 86 | + long cnt = n - idx - 1, an = x - 1, a1 = an - cnt + 1; |
| 87 | + sum += cnt * (a1 + an) / 2; |
| 88 | + } |
| 89 | + return sum <= max; |
| 90 | + } |
| 91 | +} |
| 92 | +``` |
| 93 | +* 时间复杂度:$O(\log{n})$ |
| 94 | +* 空间复杂度:$O(1)$ |
| 95 | + |
| 96 | +--- |
| 97 | + |
| 98 | +### 最后 |
| 99 | + |
| 100 | +这是我们「刷穿 LeetCode」系列文章的第 `No.1802` 篇,系列开始于 2021年01月01日,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。 |
| 101 | + |
| 102 | +在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 |
| 103 | + |
| 104 | +为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。 |
| 105 | + |
| 106 | +在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 |
| 107 | + |
0 commit comments