两个线段获得的最多奖品

2024-09-11

题目：

在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。

你可以同时选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。

  • 比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 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 <= prizePositions.length <= 105
  • 1 <= prizePositions[i] <= 109
  • 0 <= k <= 109
  • prizePositions 有序非递减。

思路：

题意：一维数轴上有 n 个点，用两条长为 k 的线段，一共最多可以覆盖多少个点？

方法一：枚举右，维护左

一条线段：
	从特殊到一般，先想想只有一条线段要怎么做。
	如果线段的右端点没有奖品，我们可以把线段左移，使其右端点恰好有奖品，这不会让线段覆盖的奖品个数变少。所以只需枚举 prizePositions[right] 为线段的右端点，然后需要算出最远（最小）覆盖的奖品的位置 prizePositions[left]，此时覆盖的奖品的个数为 right − left + 1
由于 right 变大时，left 也会变大，有单调性，可以用滑动窗口快速算出 left。
	注意：prizePositions[left] 不一定是线段的左端点。prizePositions[left] 只是最左边的被线段覆盖的那个奖品的位置，线段左端点可能比 prizePositions[left] 更小。

两条线段：
	两条线段一左一右。考虑枚举右（第二条线段），同时维护左（第一条线段）能覆盖的最多奖品个数。
	贪心地想，两条线段不相交肯定比相交更好，覆盖的奖品可能更多。
	设第二条线段右端点在 prizePositions[right] 时，最远（最小）覆盖的奖品的位置为 prizePositions[left]。
	我们需要计算在 prizePositions[left] 左侧的第一条线段最多可以覆盖多少个奖品。这可以保证两条线段不相交。
	定义 mx[i+1] 表示第一条线段右端点 ≤ prizePositions[i] 时，最多可以覆盖多少个奖品。特别地，定义 mx[0]=0。
	如何计算 mx？考虑动态规划：
	线段右端点等于 prizePositions[i] 时，可以覆盖最多的奖品，即 i − left.i + 1。其中left.i 表示右端点覆盖奖品 prizePositions[i] 时，最左边的被线段覆盖的奖品。
	线段右端点小于 prizePositions[i] 时，可以覆盖最多的奖品，这等价于右端点 ≤ prizePositions[i − 1] 时，最多可以覆盖多少个奖品，即 mx[i]。注：这里可以说明为什么状态要定义成 mx[i+1] 而不是 mx[i]，这可以避免当 i = 0 时出现 i − 1 = −1 这种情况。
二者取最大值，得 mx[i + 1]  =max(mx[i], i − left.i + 1)

上式也可以理解为 i − left.i + 1 的前缀最大值。
如何计算两条线段可以覆盖的奖品个数？
	第二条线段覆盖的奖品个数为 right − left + 1。
	第一条线段覆盖的奖品个数为线段右端点 ≤ prizePositions[left − 1] 时，最多覆盖的奖品个数，即 mx[left]。
综上，两条线段可以覆盖的奖品个数为 mx[left] + right − left + 1
枚举 right 的过程中，取上式的最大值，即为答案。

我们遍历了所有的奖品作为第二条线段的右端点，通过 mx[left] 保证第一条线段与第二条线段不相交，且第一条线段覆盖了第二条线段左侧的最多奖品。那么这样遍历后，算出的答案就一定是所有情况中的最大值。

注意：可以在计算第二条线段的滑动窗口的同时，更新和第一条线段有关的 mx。这是因为两条线段一样长，第二条线段移动到 right 时所覆盖的奖品个数，也是第一条线段移动到 right 时所覆盖的奖品个数。

小优化：如果 2k  +1 ≥ prizePositions[n − 1] − prizePositions[0]，说明所有奖品都可以被覆盖，直接返回 n。例如 prizePositions=[0, 1, 2, 3], k = 1，那么第一条线段覆盖 0 和 1，第二条线段覆盖 2 和 3，即可覆盖所有奖品。

代码：

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) {
            return n;
        }
        int ans = 0, left = 0;
        vector<int> mx(n + 1);
        for (int right = 0; right < n; right++) {
            while (prizePositions[right] - prizePositions[left] > k) {
                left++;
            }
            ans = max(ans, mx[left] + right - left + 1);
            mx[right + 1] = max(mx[right], right - left + 1);
        }
        return ans;
    }
};