📕题干

中等

在 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

示例 2：

输入：prizePositions = [1,2,3,4], k = 0
输出：2

提示：

• 1 <= prizePositions.length <= 105
• 1 <= prizePositions[i] <= 109
• 0 <= k <= 109
• prizePositions 有序非递减。

📖题解

仅此一解

💻代码

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        left = 0
        dp = [0]*n
        max_dp = 0
        result = 0
        for right in range(n):
            while prizePositions[right] - prizePositions[left] > k:
                left += 1
            counts = right - left + 1
            dp[right] = max(counts,max_dp)
            max_dp = dp[right]
            if left > 0:
                result = max(result,counts + dp[left-1])
            else:
                result = max(result,counts)
        return result

🤔思路

用left，right确定窗口的左右边界，在移动right的时候保持prizePositions[right]，prizePositions[left]间距离不超过k。计算每种窗口包含的数量，并将最大值存储于dp中。对于每种遍历right的窗口下，要使当前数量最大，需要另外一段区间取最大，即dp[left-1]。最终输出最大result。

⏱时间复杂度

O(n)