class Solution {
public:
int maximizeWin(vector<int>& prizePositions, int k) {
}
};
2555. 两个线段获得的最多奖品
在 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 <= 1051 <= prizePositions[i] <= 1090 <= k <= 109 prizePositions 有序非递减。原站题解
golang 解法, 执行用时: 59 ms, 内存消耗: 8.3 MB, 提交时间: 2024-09-11 09:31:32
func maximizeWin(prizePositions []int, k int) (ans int) {
n := len(prizePositions)
if k*2+1 >= prizePositions[n-1]-prizePositions[0] {
return n
}
mx, left, right := 0, 0, 0
for mid, p := range prizePositions {
// 把 prizePositions[mid] 视作第二条线段的左端点，计算第二条线段可以覆盖的最大奖品下标
for right < n && prizePositions[right]-p <= k {
right++
}
// 循环结束后，right-1 是第二条线段可以覆盖的最大奖品下标
ans = max(ans, mx+right-mid)
// 把 prizePositions[mid] 视作第一条线段的右端点，计算第一条线段可以覆盖的最小奖品下标
for p-prizePositions[left] > k {
left++
}
// 循环结束后，left 是第一条线段可以覆盖的最小奖品下标
mx = max(mx, mid-left+1)
}
return
}
python3 解法, 执行用时: 85 ms, 内存消耗: 27.5 MB, 提交时间: 2024-09-11 09:31:18
class Solution:
def maximizeWin(self, prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
if k * 2 + 1 >= prizePositions[-1] - prizePositions[0]:
return n
ans = mx = left = right = 0
for mid, p in enumerate(prizePositions):
# 把 prizePositions[mid] 视作第二条线段的左端点，计算第二条线段可以覆盖的最大奖品下标
while right < n and prizePositions[right] - p <= k:
right += 1
# 循环结束后，right-1 是第二条线段可以覆盖的最大奖品下标
ans = max(ans, mx + right - mid)
# 把 prizePositions[mid] 视作第一条线段的右端点，计算第一条线段可以覆盖的最小奖品下标
while p - prizePositions[left] > k:
left += 1
# 循环结束后，left 是第一条线段可以覆盖的最小奖品下标
mx = max(mx, mid - left + 1)
return ans
javascript 解法, 执行用时: 76 ms, 内存消耗: 56.8 MB, 提交时间: 2024-09-11 09:30:46
/**
* @param {number[]} prizePositions
* @param {number} k
* @return {number}
*/
var maximizeWin = function(prizePositions, k) {
const n = prizePositions.length;
if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) {
return n;
}
const mx = Array(n + 1).fill(0);
let ans = 0, left = 0;
for (let right = 0; right < n; right++) {
const p = prizePositions[right];
while (p - prizePositions[left] > k) {
left++;
}
ans = Math.max(ans, mx[left] + right - left + 1);
mx[right + 1] = Math.max(mx[right], right - left + 1);
}
return ans;
};
rust 解法, 执行用时: 11 ms, 内存消耗: 3.3 MB, 提交时间: 2024-09-11 09:30:26
impl Solution {
pub fn maximize_win(prize_positions: Vec<i32>, k: i32) -> i32 {
let n = prize_positions.len();
if k * 2 + 1 >= prize_positions[n - 1] - prize_positions[0] {
return n as _;
}
let mut ans = 0;
let mut left = 0;
let mut mx = vec![0; n + 1];
for (right, &p) in prize_positions.iter().enumerate() {
while p - prize_positions[left] > k {
left += 1;
}
ans = ans.max(mx[left] + right - left + 1);
mx[right + 1] = mx[right].max(right - left + 1);
}
ans as _
}
}
golang 解法, 执行用时: 64 ms, 内存消耗: 9.1 MB, 提交时间: 2023-02-06 10:24:16
func maximizeWin(prizePositions []int, k int) (ans int) {
pre := make([]int, len(prizePositions)+1)
left := 0
for right, p := range prizePositions {
for p-prizePositions[left] > k {
left++
}
ans = max(ans, right-left+1+pre[left])
pre[right+1] = max(pre[right], right-left+1)
}
return
}
func max(a, b int) int { if a < b { return b }; return a }
cpp 解法, 执行用时: 76 ms, 内存消耗: 54 MB, 提交时间: 2023-02-06 10:23:53
class Solution {
public:
int maximizeWin(vector<int> &prizePositions, int k) {
int ans = 0, left = 0, n = prizePositions.size(), pre[n + 1];
pre[0] = 0;
for (int right = 0; right < n; right++) {
while (prizePositions[right] - prizePositions[left] > k) ++left;
ans = max(ans, right - left + 1 + pre[left]);
pre[right + 1] = max(pre[right], right - left + 1);
}
return ans;
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 50.6 MB, 提交时间: 2023-02-06 10:23:39
class Solution {
public int maximizeWin(int[] prizePositions, int k) {
int ans = 0, left = 0, n = prizePositions.length;
int[] pre = new int[n + 1];
for (int right = 0; right < n; right++) {
while (prizePositions[right] - prizePositions[left] > k) ++left;
ans = Math.max(ans, right - left + 1 + pre[left]);
pre[right + 1] = Math.max(pre[right], right - left + 1);
}
return ans;
}
}
python3 解法, 执行用时: 316 ms, 内存消耗: 23.5 MB, 提交时间: 2023-02-06 10:23:25
'''
同向双指针，记录第一条线段的最大覆盖数
'''
class Solution:
def maximizeWin(self, prizePositions: List[int], k: int) -> int:
pre = [0] * (len(prizePositions) + 1)
ans = left = 0
for right, p in enumerate(prizePositions):
while p - prizePositions[left] > k:
left += 1
ans = max(ans, right - left + 1 + pre[left])
pre[right + 1] = max(pre[right], right - left + 1)
return ans