题目描述
在 X轴 上有一些奖品。给你一个整数数组 prizePositions
,它按照 非递减 顺序排列,其中 prizePositions[i]
是第 i
件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k
。
你可以选择两个端点为整数的线段。每个线段的长度都必须是 k
。你可以获得位置在任一线段上的所有奖品(包括线段的两个端点)。注意,两个线段可能会有相交。
- 比方说
k = 2
,你可以选择线段[1, 3]
和[2, 4]
,你可以获得满足1 <= prizePositions[i] <= 3
或者2 <= prizePositions[i] <= 4
的所有奖品i
。
请你返回在选择两个最优线段的前提下,可以获得的 最多 奖品数目。
样例
输入:prizePositions = [1,1,2,2,3,3,5], k = 2
输出:7
解释:这个例子中,你可以选择线段 [1, 3] 和 [3, 5],获得 7 个奖品。
输入:prizePositions = [1,2,3,4], k = 0
输出:2
解释:这个例子中,一个选择是选择线段 [3, 3] 和 [4, 4],获得 2 个奖品。
限制
1 <= prizePositions.length <= 10^5
1 <= prizePositions[i] <= 10^9
0 <= k <= 10^9
prizePositions
有序非递减。
算法
(双指针,枚举分界线) $O(n)$
- 假设只能选择一个线段,则可以很简单的利用双指针,找到对于 每个 终点位置 $i$ 下,尽可能小的 $j \le i$,使得区间 $[j, i]$ 符合条件。
- 同理,也可以找到对于 每个 起点位置 $i$ 下,尽可能大的 $j$,使得区间 $[j, i]$ 符合条件。
- 预处理数组 $r$,其中 $r_i$ 表示在起点位置大于等于 $i$ 的位置中,最大的符合条件的区间长度。可以通过倒序更新后缀的方式预处理。
- 接着枚举分界线,按照步骤 $1$ 中的思路,正序枚举终点位置 $i$,找到 $j$ 后,用 $[i, j]$ 的长度拼上 $r_{i + 1}$ 的长度更新答案。
时间复杂度
- 双指针预处理的时间复杂度为 $O(n)$,更新答案的时间复杂度为 $O(n)$,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储预处理数组。
C++ 代码
class Solution {
public:
int maximizeWin(vector<int>& prizePositions, int k) {
const int n = prizePositions.size();
if (prizePositions[n - 1] - prizePositions[0] <= 2 * k)
return n;
vector<int> r(n + 1);
r[n] = 0;
for (int i = n - 1, j = n - 1; i >= 0; i--) {
while (prizePositions[j] - prizePositions[i] > k)
j--;
r[i] = max(r[i + 1], j - i + 1);
}
int ans = 0;
for (int i = 0, j = 0; i < n; i++) {
while (prizePositions[i] - prizePositions[j] > k)
j++;
ans = max(ans, i - j + 1 + r[i + 1]);
}
return ans;
}
};