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 <= 10^5
  • 1 <= prizePositions[i] <= 10^9
  • 0 <= k <= 10^9
  • prizePositions 按非递减顺序排列。

解题思路

这道题的核心思路是先解决单个线段的最优解，然后考虑如何组合两个线段。

方法一：前缀最大值 + 滑动窗口

  1. 首先，我们需要能够快速计算以任意位置为右端点的长度为 k 的线段能覆盖的最大奖品数
  2. 使用滑动窗口技术，对于每个右端点位置，找到最左边能包含在长度为 k 的线段中的位置
  3. 维护一个前缀最大值数组，记录从开始到当前位置的所有可能线段中能获得的最大奖品数
  4. 对于每个位置作为第二个线段的右端点，结合前缀最大值就能得到两个线段的最优组合

算法步骤：

  • 使用双指针维护滑动窗口，确保窗口内的位置范围不超过 k
  • 计算每个位置作为右端点时单个线段能覆盖的奖品数
  • 维护前缀最大值数组，记录到当前位置为止单个线段能获得的最大奖品数
  • 枚举第二个线段的位置，结合前缀最大值计算两个线段的最大收益

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是奖品数量。

代码实现

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        vector<int> prefix(n, 0);
        int left = 0, maxPrizes = 0;
        
        for (int right = 0; right < n; right++) {
            // 调整左边界，确保窗口长度不超过k
            while (prizePositions[right] - prizePositions[left] > k) {
                left++;
            }
            
            // 当前窗口大小
            int currentPrizes = right - left + 1;
            maxPrizes = max(maxPrizes, currentPrizes);
            
            // 更新前缀最大值
            prefix[right] = maxPrizes;
        }
        
        // 计算两个线段的最大收益
        int result = 0;
        left = 0;
        
        for (int right = 0; right < n; right++) {
            // 调整左边界
            while (prizePositions[right] - prizePositions[left] > k) {
                left++;
            }
            
            int currentPrizes = right - left + 1;
            int prevMax = (left > 0) ? prefix[left - 1] : 0;
            result = max(result, currentPrizes + prevMax);
        }
        
        return result;
    }
};

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        prefix = [0] * n
        left = 0
        max_prizes = 0
        
        # 计算前缀最大值
        for right in range(n):
            # 调整左边界，确保窗口长度不超过k
            while prizePositions[right] - prizePositions[left] > k:
                left += 1
            
            # 当前窗口大小
            current_prizes = right - left + 1
            max_prizes = max(max_prizes, current_prizes)
            
            # 更新前缀最大值
            prefix[right] = max_prizes
        
        # 计算两个线段的最大收益
        result = 0
        left = 0
        
        for right in range(n):
            # 调整左边界
            while prizePositions[right] - prizePositions[left] > k:
                left += 1
            
            current_prizes = right - left + 1
            prev_max = prefix[left - 1] if left > 0 else 0
            result = max(result, current_prizes + prev_max)
        
        return result

public class Solution {
    public int MaximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.Length;
        int[] prefix = new int[n];
        int left = 0, maxPrizes = 0;
        
        // 计算前缀最大值
        for (int right = 0; right < n; right++) {
            // 调整左边界，确保窗口长度不超过k
            while (prizePositions[right] - prizePositions[left] > k) {
                left++;
            }
            
            // 当前窗口大小
            int currentPrizes = right - left + 1;
            maxPrizes = Math.Max(maxPrizes, currentPrizes);
            
            // 更新前缀最大值
            prefix[right] = maxPrizes;
        }
        
        // 计算两个线段的最大收益
        int result = 0;
        left = 0;
        
        for (int right = 0; right < n; right++) {
            // 调整左边界
            while (prizePositions[right] - prizePositions[left] > k) {
                left++;
            }
            
            int currentPrizes = right - left + 1;
            int prevMax = (left > 0) ? prefix[left - 1] : 0;
            result = Math.Max(result, currentPrizes + prevMax);
        }
        
        return result;
    }
}

var maximizeWin = function(prizePositions, k) {
    const n = prizePositions.length;
    const prefix = new Array(n).fill(0);
    let left = 0, maxPrizes = 0;
    
    // 计算前缀最大值
    for (let right = 0; right < n; right++) {
        // 调整左边界，确保窗口长度不超过k
        while (prizePositions[right] - prizePositions[left] > k) {
            left++;
        }
        
        // 当前窗口大小
        const currentPrizes = right - left + 1;
        maxPrizes = Math.max(maxPrizes, currentPrizes);
        
        // 更新前缀最大值
        prefix[right] = maxPrizes;
    }
    
    // 计算两个线段的最大收益
    let result = 0;
    left = 0;
    
    for (let right = 0; right < n; right++) {
        // 调整左边界
        while (prizePositions[right] - prizePositions[left] > k) {
            left++;
        }
        
        const currentPrizes = right - left + 1;
        const prevMax = (left > 0) ? prefix[left - 1] : 0;
        result = Math.max(result, currentPrizes + prevMax);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
前缀最大值 + 滑动窗口O(n)O(n)

其中 n 是 prizePositions 数组的长度。虽然有嵌套循环，但内层 while 循环的总执行次数不超过 n，因此整体时间复杂度仍为 O(n)。

相关题目