题目描述
在X轴上有一些奖品。给你一个整数数组$prizePositions$,它按照 非递减 顺序排列,其中$prizePositions[i]$是第 $i$件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数$k$。
你可以选择两个端点为整数的线段。每个线段的长度都必须是$k$。你可以获得位置在任一线段上的所有奖品(包括线段的两个端点)。注意,两个线段可能会有相交。
- 比方说$k = 2$,你可以选择线段$[1, 3]$和$[2, 4]$,你可以获得满足$1 \leq prizePositions[i] \leq 3$或者$2 \leq prizePositions[i] \leq 4$的所有奖品$i$。
请你返回在选择两个最优线段的前提下,可以获得的最多奖品数目。
示例$1$:
输入:prizePositions = [1,1,2,2,3,3,5], k = 2
输出:7
解释:这个例子中,你可以选择线段 [1, 3] 和 [3, 5] ,获得 7 个奖品。
示例$2$:
输入:prizePositions = [1,2,3,4], k = 0
输出:2
解释:这个例子中,一个选择是选择线段 [3, 3] 和 [4, 4] ,获得 2 个奖品。
提示:
- $1 \leq prizePositions.length \leq 10^5$
- $1 \leq prizePositions[i] \leq 10^9$
- $0 \leq k \leq 10^9$
- $prizePositions$有序非递减。
算法
二分查找+前后缀最值
如果以$prizePosition[i]$为一根线段的左端点,那么长度为$k$的线段最后能覆盖的位置就是最后一个能满足$prizePosition[j]-prizePosition[i] \leq k$的$prizePosition[j]$(其中$i \leq j$),这个$j$可以通过二分查找确定出来,而这跟线段包含的奖品数就是$j-i+1$。
因此分为两种情况:
- 两根线段有重叠:每次确定左端点$prizePosition[i]$,然后以长度$2k$通过二分查找确定右端点$j$。如果查找出来的$j$满足$j-i+1 \lt 2k$,说明两根线段重叠。遍历左端点,就能确定两根线段有重叠时的奖品最大数量。
- 两根线段不重叠:可以利用前后缀最值配合二分查找,预处理出两个数组$left$和$right$,$left[i]$表示$[0,i]$中长度为$k$的线段包含的最大奖品数;$right[i]$表示$[i,n)$中长度为$k$的线段包含的最大奖品数。最后遍历$i$,这种情况下两根线段覆盖的最大奖品数量即为$max(max_{i=1}^{n-1}(left[i-1]+right[i]), right[0], left[n-1])$。
总体上两根线段所覆盖的奖品数量最大值就是$1$和$2$两种情况中的较大值。
复杂度分析
遍历线段的某个端点时,时间复杂度为$O(n)$,而对于每个固定的端点,二分查找另一个端点时间复杂度为$O(log_2n)$,因此整体的时间复杂度为$O(nlog_2n)$。
开辟了$left$和$right$两个辅助数组,额外空间复杂度为$O(n)$。
C++ 代码
typedef long long LL;
class Solution {
public:
int maximizeWin(vector<int>& prizePositions, int k) {
int n = prizePositions.size();
if(n == 1) return 1;
int res = 0;
// 两个线段有重叠的情况
for(int i = 0; i < n; i++) {
res = max(res, (int)(upper_bound(prizePositions.begin() + i, prizePositions.end(), (LL)prizePositions[i] + 2*k) - prizePositions.begin()) - i);
}
// 两个线段不重叠的情况
res = max(res, solve(prizePositions, k));
return res;
}
int solve(vector<int>& nums, int k) {
int n = nums.size();
vector<int> right(n), left(n);
// right[i]表示[i,n)中长度为k的线段包含的最大奖品数
for(int i = n - 1; i >= 0; i--) {
right[i] = max(i < n - 1? right[i + 1]: 0, (int)(upper_bound(nums.begin() + i, nums.end(), nums[i] + k) - nums.begin()) - i);
}
// left[i]表示[0,i]中长度为k的线段包含的最大奖品数
for(int i = 0; i < n; i++) {
left[i] = max(i? left[i - 1]: 0, i - (int)(lower_bound(nums.begin(), nums.begin() + i + 1, nums[i] - k) - nums.begin()) + 1);
}
int res = left.back();
for(int i = 0; i < n; i++) {
res = max(res, (i? left[i - 1]: 0) + right[i]);
}
return res;
}
};