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

【LetMeFly】2555.两个线段获得的最多奖品：动态规划+滑动窗口

力扣题目链接：https://leetcode.cn/problems/maximize-win-from-two-segments/

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

解题方法：动态规划+滑动窗口

使用一个数组$dp$，其中$dp[i]$表示前$i$个元素中一条线至多覆盖多少个元素。怎么确定一条线之多能覆盖多少个元素？滑动窗口即可。

使用两个指针$l$和$r$分别指向直线覆盖的最左元素和最右元素。每次$r$后移一位，若长度超过$k$则不断右移$l$直至长度$\leq k$。

这样，我们就得到了以第$r+1$个元素为直线右端点的直线最多覆盖多少个元素。同时更新$dp$数组即可得到前$i$个元素中一条线至多覆盖多少个元素。

但是这道题有两条线。两条线好说：

以类似的方法（双指针的滑动窗口）确定第二条线右端点为$prizePositions[r]$时的最大覆盖数量，加上$dp[l]$就变成了两条线的最大覆盖数量了（没有人想让两条线有重叠吧）

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

AC代码

C++

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        vector<int> dp(prizePositions.size() + 1);
        int ans = 0;
        for (int l = 0, r = 0; r < prizePositions.size(); r++) {
            while (prizePositions[r] - prizePositions[l] > k) {
                l++;
            }
            ans = max(ans, r - l + 1 + dp[l]);
            dp[r + 1] = max(dp[r], r - l + 1);
        }
        return ans;
    }
};

Python

from typing import List

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        ans = 0
        dp = [0] * (len(prizePositions) + 1)
        l, r = 0, 0
        while r < len(prizePositions):
            while prizePositions[r] - prizePositions[l] > k:
                l += 1
            ans = max(ans, r - l + 1 + dp[l])
            dp[r + 1] = max(dp[r], r - l + 1)
            r += 1
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/142149662