两个线段获得的最多奖品

难度:

标签:

题目描述

There are some prizes on the X-axis. You are given an integer array prizePositions that is sorted in non-decreasing order, where prizePositions[i] is the position of the i^th prize. There could be different prizes at the same position on the line. You are also given an integer k.

You are allowed to select two segments with integer endpoints. The length of each segment must be k. You will collect all prizes whose position falls within at least one of the two selected segments (including the endpoints of the segments). The two selected segments may intersect.

For example if k = 2, you can choose segments [1, 3] and [2, 4], and you will win any prize i that satisfies 1 <= prizePositions[i] <= 3 or 2 <= prizePositions[i] <= 4.

Return the maximum number of prizes you can win if you choose the two segments optimally.

Example 1:

Input: prizePositions = [1,1,2,2,3,3,5], k = 2
Output: 7
Explanation: In this example, you can win all 7 prizes by selecting two segments [1, 3] and [3, 5].

Example 2:

Input: prizePositions = [1,2,3,4], k = 0
Output: 2
Explanation: For this example, one choice for the segments is [3, 3] and [4, 4], and you will be able to get 2 prizes.

Constraints:

1 <= prizePositions.length <= 10⁵
1 <= prizePositions[i] <= 10⁹
0 <= k <= 10⁹
prizePositions is sorted in non-decreasing order.

代码结果

运行时间: 67 ms, 内存: 26.9 MB

/*
 * 思路：
 * 1. 使用流来处理数组。
 * 2. 计算以每个位置为起点的长度为k的线段内的奖品数量。
 * 3. 使用流和滑动窗口来计算在不重叠的情况下，两个线段内的最大奖品数量。
 * 4. 返回最大值。
 */
import java.util.stream.IntStream;

public class Solution {
    public int maxPrizes(int[] prizePositions, int k) {
        int n = prizePositions.length;
        int[] count = IntStream.range(0, n).map(i -> {
            int j = i;
            while (j < n && prizePositions[j] <= prizePositions[i] + k) {
                j++;
            }
            return j - i;
        }).toArray();

        return IntStream.range(0, n).flatMap(i -> IntStream.range(i + count[i], n).map(j -> count[i] + count[j])).max().orElse(0);
    }
}

解释

方法:

这个题解采用的是一种贪心加滑动窗口的方法。首先，特殊情况判断：如果两个长度为k的线段加上中间至少一个单位的间隔仍然小于整个奖品分布的跨度，则说明所有奖品都可以在两个线段内被覆盖，直接返回所有奖品的数量。在一般情况下，使用滑动窗口来确定每个位置结尾的线段可以覆盖的最多奖品数量，并记录下来。同时，通过维护一个pre数组，记录以每个位置结尾时前一个线段可以覆盖的最多奖品数量。最终，通过比较，找到两个线段可以覆盖的最大奖品数量。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

请问在计算两个线段覆盖的最大奖品数时，为什么可以通过简单地将两个线段的奖品数相加得到结果？是否需要考虑两个线段的重叠部分？

▷

在计算两个线段覆盖的最大奖品数时，题解中通过使用滑动窗口和前缀数组来确保不会简单地相加两个线段的奖品数，而是考虑了两个线段可能的重叠。在计算过程中，我们通过维护一个pre数组来记录前一个线段可以覆盖的最多奖品数量，并结合当前线段的覆盖，从而确保了不会重复计算重叠部分的奖品。具体来说，每个位置在更新最大奖品数时，已经考虑了与之前线段的组合，避免了重复计数的问题。

🦆

在题解中提到的特殊情况`如果两个长度为k的线段加上中间至少一个单位的间隔仍然小于整个奖品分布的跨度`，这里的逻辑是否有误？应该是`小于等于`还是`小于`整个奖品分布的跨度？

▷

题解中的表述中有一定的误区。正确的逻辑应该是考虑如果两个长度为k的线段加上中间至少一个单位的间隔仍然可以覆盖整个奖品分布的跨度时的情况。因此，应该使用`小于等于`来描述这种情况。如果两个线段的总长度加上至少一个单位的间隔小于等于奖品分布的最大跨度，那么可以直接覆盖所有奖品。

🦆

题解中使用的滑动窗口方法，如何确保在移动左指针时，不会错过某些可能的最优解？

▷

滑动窗口算法通过动态调整左右指针来维持窗口内的最优状态。在题解中，右指针right逐步向右移动，而左指针left只有在窗口大小超出了长度k时才向右移动。这种方法确保了在每个可能的右端点位置，左端点都调整到了能使当前窗口大小不超过k的最远位置。由于这种逐步调整保持了窗口内元素数量的最大化，它可以确保不会错过任何可能的最优解。

🦆

在更新`pre`数组时，为什么选择`pre[right + 1] = max(pre[right], right - left + 1)`，这里的`right - left + 1`具体代表什么含义？

▷

`right - left + 1`代表的是当前滑动窗口内的奖品数量，即从位置left到位置right（包括两端）的奖品总数。在更新pre数组时，`pre[right + 1] = max(pre[right], right - left + 1)`操作是为了将当前最优的线段奖品覆盖数存储起来，以便后续的计算可以利用。这样，pre数组在位置right+1记录的值表示在考虑到位置right时，一个线段能覆盖的最大奖品数。这是一个步骤，确保计算两个线段时可以快速获取前一个线段的最优结果。

两个线段获得的最多奖品

题目描述

代码结果

解释

代码细节讲解

相关问题