两个线段获得的最多奖品

标签: 数组 二分查找 滑动窗口

难度: Medium

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

Submission

运行时间: 67 ms

内存: 26.9 MB

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        # 所有奖品都能选的特殊情况
        if k + k + 1 >= prizePositions[-1] - prizePositions[0]:
            return n

        pre = [0] * (n + 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

Explain

这个题解采用的是一种贪心加滑动窗口的方法。首先，特殊情况判断：如果两个长度为k的线段加上中间至少一个单位的间隔仍然小于整个奖品分布的跨度，则说明所有奖品都可以在两个线段内被覆盖，直接返回所有奖品的数量。在一般情况下，使用滑动窗口来确定每个位置结尾的线段可以覆盖的最多奖品数量，并记录下来。同时，通过维护一个pre数组，记录以每个位置结尾时前一个线段可以覆盖的最多奖品数量。最终，通过比较，找到两个线段可以覆盖的最大奖品数量。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        # 处理特殊情况：两个长度为k的线段可以覆盖所有奖品
        if k + k + 1 >= prizePositions[-1] - prizePositions[0]:
            return n

        pre = [0] * (n + 1) # 记录每个位置为结束点的线段可以覆盖的最多奖品数
        ans = left = 0
        for right, p in enumerate(prizePositions):
            while p - prizePositions[left] > k:
                left += 1  # 移动左指针，直到窗口大小不超过k
            ans = max(ans, right - left + 1 + pre[left]) # 更新两个线段可以获得奖品的最大数量
            pre[right + 1] = max(pre[right], right - left + 1) # 更新pre数组，为后续的线段选择做准备
        return ans

Explore

在计算两个线段覆盖的最大奖品数时，题解中通过使用滑动窗口和前缀数组来确保不会简单地相加两个线段的奖品数，而是考虑了两个线段可能的重叠。在计算过程中，我们通过维护一个pre数组来记录前一个线段可以覆盖的最多奖品数量，并结合当前线段的覆盖，从而确保了不会重复计算重叠部分的奖品。具体来说，每个位置在更新最大奖品数时，已经考虑了与之前线段的组合，避免了重复计数的问题。

题解中的表述中有一定的误区。正确的逻辑应该是考虑如果两个长度为k的线段加上中间至少一个单位的间隔仍然可以覆盖整个奖品分布的跨度时的情况。因此，应该使用`小于等于`来描述这种情况。如果两个线段的总长度加上至少一个单位的间隔小于等于奖品分布的最大跨度，那么可以直接覆盖所有奖品。

滑动窗口算法通过动态调整左右指针来维持窗口内的最优状态。在题解中，右指针right逐步向右移动，而左指针left只有在窗口大小超出了长度k时才向右移动。这种方法确保了在每个可能的右端点位置，左端点都调整到了能使当前窗口大小不超过k的最远位置。由于这种逐步调整保持了窗口内元素数量的最大化，它可以确保不会错过任何可能的最优解。

`right - left + 1`代表的是当前滑动窗口内的奖品数量，即从位置left到位置right（包括两端）的奖品总数。在更新pre数组时，`pre[right + 1] = max(pre[right], right - left + 1)`操作是为了将当前最优的线段奖品覆盖数存储起来，以便后续的计算可以利用。这样，pre数组在位置right+1记录的值表示在考虑到位置right时，一个线段能覆盖的最大奖品数。这是一个步骤，确保计算两个线段时可以快速获取前一个线段的最优结果。