当前位置：首页 > article >正文

力扣刷题之2555.两个线段获得的最多奖品

article 2024/11/18 14:35:35

题干描述

在 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 个奖品。

题干解析

这个题干要求我们在数轴上找到两个长度为k的线段，使得它们覆盖的奖品最多。线段之间可以重叠，但是为了获得最优解，我们需要计算出能够覆盖的奖品数量最大化的方案。

核心思路

这道题我们打算使用动态规划法，理由如下：

这个问题的结构使得其每一步的最有解依赖于之前的计算结果，具体来说就是，若使用动态规划法可以帮助我们高效地解决两个非完全重叠的长度为k的线段所能覆盖的最大奖品数问题。

1.滑动窗口：

我们可以使用两个滑动窗口来模拟两个长度为k的线段。每个滑动窗口代表一个线段，并计算线段内能够获得的奖品数量最大化的方案。

2.累积最大值：

因为我们需要考虑两个不重叠线段的最优组合，因此我们可以维护一个动态规划数组dp，用来记录每一个位置之前的线段能够覆盖的最大奖品数量。

3.相交的处理：

两个线段可能会有重叠的部分，因此我们要在动态规划的过程中考虑到线段的重叠情况，保证在取得两个线段时，总奖品数量最大。

详细解题思路

1.初始化：

我们创建一个dp数组，dp[i]表示在第i位置之前，能够选择的最有线段所覆盖的奖品数量。

2.滑动窗口的运用：

对于每个奖品位置prizePositions[i]，我们将该位置作为一个活动窗口的右端点，计算出它能够覆盖的奖品数。
我们不断调整滑动窗口的左端点left，确保滑动窗口的长度不超过k。

3.两个线段的最优选择：

我们在动态规划过程中记录着两个线段的选择

第一个线段通过滑动窗口计算当前的奖品数量。
第二个线段则利用dp[left]，表示当前线段左边能获得的最大奖品数量
通过组合两个不重叠食物线段，计算当前的最大奖品数，并更新全局的最大值。

4.返回结果：

最终返回两个线段能够覆盖的奖品的最大数量。

代码实现

#include <stdio.h>
#include <stdlib.h>

//计算在选择两个长度为k的线段的情况下，最多能获得的奖品数量
int maximizeWin(int* prizePositions, int prizePositionsSize, int k){
    //动态规划数组，用来记录当前线段之前的最大覆盖奖品数
    int* dp = (int*)malloc((prizePositionsSize + 1) * sizeof(int));
    
     //初始化dp数组
     for(int i = 0; i <= prizePositionsSize; ++i){
         dp[i] = 0;
     }
 
     int left = 0;//滑动窗口的左边界
     int maxCount = 0;//记录最大奖品数
     //遍历所有奖品的位置
     for(int right = 0; right < prizePositionsSize; ++right){
        //保证当前窗口内的长度不超过k
        while(prizePositions[right] - prizePositions[left] > k){
             left++;
        }
        //当前线段覆盖的奖品数
        int currentPrizes = right - left + 1;
        //使用动态规划保存两个线段不完全重叠的最大奖品数
        dp[right + 1] = dp[right] > currentPrizes ? dp[right] : currentPrizes;
         // 计算两个线段的最大奖品数（左边的最大 + 当前线段）
        int totalPrizes = dp[left] + currentPrizes;
        maxCount = maxCount > totalPrizes ? maxCount : totalPrizes;
     }
      // 释放动态分配的内存
    free(dp);
    
    return maxCount;
}