2555-两个线段获得的最多奖品

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

在 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 有序非递减。

本题视频讲解

见【双周赛 97】 的第三题。

前置知识：同向双指针

见 同向双指针【基础算法精讲 01】 。

注：我一般把窗口大小不固定的叫做双指针，窗口大小固定的叫做滑动窗口。

思路

我们可以强制让第二条线段的右端点恰好落在奖品上，设第二条线段右端点在 prizePositions}[\textit{right}] 时，左端点最远覆盖了 prizePositions}[\textit{left}]，我们需要知道在 prizePositions}[\textit{left}] 左侧的第一条线段最多可以覆盖多少个奖品。

那么，先想想只有一条线段要怎么做。

使用双指针，设线段右端点在 prizePositions}[\textit{right}] 时，左端点最远覆盖了 prizePositions}[\textit{left}]，那么当前覆盖的奖品个数为 right} - \textit{left} + 1。

同时，用一个数组 pre}[\textit{right}+1] 记录线段右端点不超过 prizePositions}[\textit{right}] 时最多可以覆盖多少个奖品。下标错开一位是为了方便下面计算。

初始 pre}[0]=0。根据 pre 的定义，有

\textit{pre}[\textit{right}+1] = \max(\textit{pre}[\textit{right}],\textit{right} - \textit{left} + 1)

回到第二条线段的计算，根据开头说的，此时最多可以覆盖的奖品数为

\textit{right}-\textit{left}+1+\textit{pre}[\textit{left}]

这里 pre}[\textit{left}] 表示第一条线段右端点不超过 prizePositions}[\textit{left}-1] 时最多可以覆盖多少个奖品。

遍历过程中取上式的最大值，即为答案。

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

如果脑中没有一幅直观的图像，可以看看 视频讲解【双周赛 97】 的第三题。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        pre = [0] * (len(prizePositions) + 1)
        ans = left = 0
        for right, p in enumerate(prizePositions):
            while p - prizePositions[left] > k:
                left += 1
            ans = max(ans, right - left + 1 + pre[left])
            pre[right + 1] = max(pre[right], right - left + 1)
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maximizeWin(int[] prizePositions, int k) {
        int ans = 0, left = 0, n = prizePositions.length;
        int[] pre = new int[n + 1];
        for (int right = 0; right < n; right++) {
            while (prizePositions[right] - prizePositions[left] > k) ++left;
            ans = Math.max(ans, right - left + 1 + pre[left]);
            pre[right + 1] = Math.max(pre[right], right - left + 1);
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maximizeWin(vector<int> &prizePositions, int k) {
        int ans = 0, left = 0, n = prizePositions.size(), pre[n + 1];
        pre[0] = 0;
        for (int right = 0; right < n; right++) {
            while (prizePositions[right] - prizePositions[left] > k) ++left;
            ans = max(ans, right - left + 1 + pre[left]);
            pre[right + 1] = max(pre[right], right - left + 1);
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maximizeWin(prizePositions []int, k int) (ans int) {
	pre := make([]int, len(prizePositions)+1)
	left := 0
	for right, p := range prizePositions {
		for p-prizePositions[left] > k {
			left++
		}
		ans = max(ans, right-left+1+pre[left])
		pre[right+1] = max(pre[right], right-left+1)
	}
	return
}

func max(a, b int) int { if a < b { return b }; return a }

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 prizePositions 的长度。虽然写了个二重循环，但是内层循环中对 left 加一的总执行次数不会超过 n 次，所以总的时间复杂度为 O(n)。
  • 空间复杂度：O(n)。

相似题目（同向双指针）

 Comments
On this page
2555-两个线段获得的最多奖品
  1. 本题视频讲解
  2. 前置知识：同向双指针
  3. 思路
  4. 复杂度分析