题目描述：
在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。
你可以选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。
- 比方说
k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。
请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。
数据范围：
$1\le prize.len \le 10^5, 1\le prize[i] \le 10^9, 0 \le k\le 10^9$
题解：
首先肯定能确定的是，两条区间最好没有交集。当然放不下第二条时，可以认为第二条线段的长度小于 $k$ 。
然后可以先使用滑动窗口处理出来一条线段能覆盖多少，然后可以求前缀最大值。
然后枚举第二条线段的左端点，然后使用滑动窗口得到第二条线段的覆盖数，并且可以快速查询第一条线段覆盖数最大值。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int maximizeWin(vector<int> &prizePositions, int k)
{
int n = prizePositions.size();
vector<int> left(n);
int l = 0, r;
for (int r = 0; r < n; ++r)
{
while (prizePositions[r] - prizePositions[l] > k)
++l;
left[r] = r - l + 1;
if(r >= 1)
left[r] = max(left[r], left[r - 1]);
}
r = l = 1;
int ans = 1;
for (r = 1; r < n; ++r)
{
while (prizePositions[r] - prizePositions[l] > k)
++l;
ans = max(ans, left[l - 1] + r - l + 1);
}
return ans;
}
};
|