贪心+滑窗+递推，LeetCode 2555. 两个线段获得的最多奖品

一、题目

1、题目描述

2、接口描述

python3

 ​

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:

cpp

 ​

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        std::vector<int> pre(n);
        int res = 0;
        for (int j = 0, i = 0; j < n; ++ j) {
            while (prizePositions[j] - prizePositions[i] > k) ++ i;
            res = std::max(res, j - i + 1 + pre[i]);
            if (j + 1 < n)
                pre[j + 1] = std::max(pre[j], j - i + 1);
        }
        return res;
    }
};

C#

 ​

public class Solution
{
    public int MaximizeWin(int[] prizePositions, int k)
    {

    }
}

3、原题链接

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

二、解题报告

1、思路分析

考虑最优解的两个线段会相交吗？

不会，我们总能将两个相交线段分开来得到更优解

我们考虑滑窗维护当前线段[i, j]，在过程中维护答案 res = max(res, j - i + 1 + pre[i])

pre[i] 指 [0, i) 内的最长线段

pre[] 可以在滑窗 的过程中递推

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

python3

 ​

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        pre = [0] * n
        res = i = 0
        for j in range(n):
            while prizePositions[j] - prizePositions[i] > k:
                i += 1
            res = max(res, j - i + 1 + pre[i])
            if j + 1 < n:
                pre[j + 1] = max(pre[j], j - i + 1)
        return res

cpp

 ​

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        std::vector<int> pre(n);
        int res = 0;
        for (int j = 0, i = 0; j < n; ++ j) {
            while (prizePositions[j] - prizePositions[i] > k) ++ i;
            res = std::max(res, j - i + 1 + pre[i]);
            if (j + 1 < n)
                pre[j + 1] = std::max(pre[j], j - i + 1);
        }
        return res;
    }
};

C#

 ​

public class Solution
{
    public int MaximizeWin(int[] prizePositions, int k)
    {
        int n = prizePositions.Length;
        int[] pre = new int[n];
        int res = 0;
        for (int j = 0, i = 0; j < n; ++ j)
        {
            while (prizePositions[j] - prizePositions[i] > k)
                ++i;
            res = Math.Max(res, j - i + 1 + pre[i]);
            if (j + 1 < n)
                pre[j + 1] = Math.Max(j - i + 1, pre[j]);
        }
        return res;
    }
}