What is the main approach for Maximize Win From Two Segments?

Use a sliding window to count prizes in segments and binary search to combine two segments for maximum coverage.

Can segments overlap in this problem?

Yes, segments can intersect, and prizes in the overlap should be counted only once for total maximization.

How do you handle large prizePositions arrays efficiently?

Sliding window with precomputed maximums from the right ensures O(n) iteration, avoiding O(n^2) checks.

Why is binary search needed for this problem?

Binary search helps quickly find the farthest valid right segment to pair with a left segment, maximizing prizes.

How does GhostInterview solve the pattern of two segments?

It automatically computes optimal single and paired segments using the sliding window plus binary search pattern, showing exact prize counts.

#2555

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

两个线段获得的最多奖品

在 X轴上有一些奖品。给你一个整数数组 prizePositions ，它按照非递减顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。你可以同时选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位…

数组二分查找滑动窗口

题目描述

在 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 <= 10⁵
1 <= prizePositions[i] <= 10⁹
0 <= k <= 10⁹
prizePositions 有序非递减。

lightbulb

解题思路

方法一：动态规划 + 二分查找

我们定义 $f[i]$ 表示在前 $i$ 个奖品中，选择一个长度为 $k$ 的线段，可以获得的最多奖品数目。初始时 $f[0] = 0$ 。定义答案变量 $ans = 0$ 。

接下来，我们枚举每个奖品的位置 $x$ ，通过二分查找，找到最左边的奖品下标 $j$ ，使得 $prizePositions[j] \geq x - k$ 。此时，我们更新答案 $ans = \max(ans, f[j] + i - j)$ ，并更新 $f[i] = \max(f[i - 1], i - j)$ 。

最后，返回 $ans$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为奖品数目。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        f = [0] * (n + 1)
        ans = 0
        for i, x in enumerate(prizePositions, 1):
            j = bisect_left(prizePositions, x - k)
            ans = max(ans, f[j] + i - j)
            f[i] = max(f[i - 1], i - j)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) with sliding windows and precomputation, while binary search ensures efficient selection of segment pairs. Space complexity is O(n) for storing maximums from the right.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you considering overlapping segments correctly?
question_mark
Have you tried computing maximum prizes from the right to pair efficiently?
question_mark
Can you optimize selection with binary search over segment endpoints?

warning

常见陷阱

外企场景

error
Forgetting segments can overlap and double-counting prizes.
error
Not precomputing maximum prizes from the right, leading to inefficient O(n^2) solutions.
error
Misapplying sliding window logic when k = 0 or segments touch endpoints.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize win with three segments of fixed length.
arrow_right_alt
Change segment lengths dynamically for each selection.
arrow_right_alt
Prizes are on a 2D plane with axis-aligned segments.

help

常见问题

外企场景

继续练习

#2528 最大化城市的最小电量 #2411 按位或最大的最小子数组长度 #2398 预算内的最多机器人数目