LC-6331.两个线段获得的最多奖品

题目描述

leetcode 中等题

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

提示1：

1 <= prizePositions.length <= 10^5
1 <= prizePositions[i] <= 10^9
0 <= k <= 10^9
prizePositions 有序非递减。

双指针

考虑只需要选择一条线段的情况，此时显然可以用双指针在 $O(N)$ 复杂度内解决，设左右指针分别为 $left、right$ 。

再考虑第二条线段如何选择，不妨设第一条线段是右边的线段。那么为了使奖品最多，第二条线段的右端点必然在 $left$ 的左边，那么我们可以预处理出一个数组 $rightPointMax$ ，其中第 $i + 1$ 位表示右端点在 $i$ 及 $i$ 左边时能取到的最大奖品。

第一条线段能取到的奖品数量为 $right - left + 1$ ，第二条线段最多能取到的数量为 $rightPointMax[left - 1 + 1]$ ，只需要枚举第一条线段的所有可能性并取 $max(right - left + 1 + rightPointMax[left - 1 + 1])$ 即为答案。

class Solution {
    public int maximizeWin(int[] arr, int k) {
        int n = arr.length;
        long[] rightPointMax = new long[n + 1];
        long ans = 0;
        for(int left = 0, right = 0; right < n; right++){
            while(arr[right] - arr[left] > k){
                left++;
            }
            rightPointMax[right + 1] = Math.max(rightPointMax[right], right - left + 1);
            ans = Math.max(ans, rightPointMax[left] + right - left + 1);
        }
        return (int)ans;
    }
}