What is the main strategy to solve Maximum Fruits Harvested After at Most K Steps?

Use binary search to find reachable intervals combined with sliding window and prefix sums to efficiently compute maximum harvest totals.

Can moving left then right yield more fruits than only moving in one direction?

Yes, optimal paths often involve moving one way, turning, and collecting additional fruits without exceeding k steps.

Is sorting the fruits array necessary?

Yes, sorting ensures the sliding window and prefix sum techniques work correctly to evaluate all valid intervals.

How do prefix sums improve performance in this problem?

Prefix sums allow instant calculation of total fruits in any interval, avoiding repeated summation and reducing time complexity to O(n).

What common errors should be avoided?

Avoid exceeding k steps when summing intervals, ignoring the turn in path, or recomputing sums inefficiently instead of using prefix sums.

#2106

Hard

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

LeetCode 题解工作台

摘水果

在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [position i , amount i ] 表示共有 amount i 个水果放置在 position i 上。 fruits 已经按 position i 升序排列 …

数组二分查找滑动窗口前缀和

题目描述

在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [position_i, amount_i] 表示共有 amount_i 个水果放置在 position_i 上。fruits 已经按 position_i 升序排列 ，每个 position_i 互不相同 。

另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作一步。你总共可以走最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。

返回你可以摘到水果的 最大总数 。

示例 1：

输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：
最佳路线为：
- 向右移动到位置 6 ，摘到 3 个水果
- 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果

示例 2：

输入：fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输出：14
解释：
可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。
最佳路线为：
- 在初始位置 5 ，摘到 7 个水果
- 向左移动到位置 4 ，摘到 1 个水果
- 向右移动到位置 6 ，摘到 2 个水果
- 向右移动到位置 7 ，摘到 4 个水果
移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果

示例 3：

输入：fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输出：0
解释：
最多可以移动 k = 2 步，无法到达任一有水果的地方

提示：

1 <= fruits.length <= 10⁵
fruits[i].length == 2
0 <= startPos, position_i <= 2 * 10⁵
对于任意 i > 0 ，position_i-1 < position_i 均成立（下标从 0 开始计数）
1 <= amount_i <= 10⁴
0 <= k <= 2 * 10⁵

lightbulb

解题思路

方法一：双指针

我们不妨假设移动的位置区间为 $[l, r]$ ，开始位置为 $\textit{startPos}$ ，来看看如何算出移动的最小步数。根据 $\textit{startPos}$ 所处的位置，我们可以分为三种情况：

如果 $\textit{startPos} \leq l$ ，那么就是从 $\textit{startPos}$ 一直向右移动到 $r$ 。移动的最小步数为 $r - \textit{startPos}$ ；
如果 $\textit{startPos} \geq r$ ，那么就是从 $\textit{startPos}$ 一直向左移动到 $l$ 。移动的最小步数为 $\textit{startPos} - l$ ；
如果 $l < \textit{startPos} < r$ ，那么可以从 $\textit{startPos}$ 向左移动到 $l$ ，再向右移动到 $r$ ；也可以从 $\textit{startPos}$ 向右移动到 $r$ ，再向左移动到 $l$ 。移动的最小步数为 $r - l + \min(\lvert \textit{startPos} - l \rvert, \lvert r - \textit{startPos} \rvert)$ 。

以上三种情况可以统一用式子 $r - l + \min(\lvert \textit{startPos} - l \rvert, \lvert r - \textit{startPos} \rvert)$ 表示。

假设我们固定区间右端点 $r$ ，向右移动左端点 $l$ ，我们来看看最小移动步数是怎么变化的。

如果 $\textit{startPos} \leq l$ ，随着 $l$ 的增大，最小步数不会发生变化。
如果 $\textit{startPos} > l$ ，随着 $l$ 的增大，最小步数会减小。

因此，随着 $l$ 的增大，最小移动步数一定是非严格单调递减的。基于此，我们可以使用双指针的方法，找出所有符合条件的最大区间，然后取所有符合条件的区间中水果总数最大的一个作为答案。

具体地，我们用两个指针 $i$ 和 $j$ 分别指向区间的左右下标，初始时 $i = j = 0$ 。另外用一个变量 $s$ 记录区间内的水果总数，初始时 $s = 0$ 。

每次我们将 $j$ 加入区间中，然后更新 $s = s + \textit{fruits}[j][1]$ 。如果此时区间内的最小步数 $\textit{fruits}[j][0] - \textit{fruits}[i][0] + \min(\lvert \textit{startPos} - \textit{fruits}[i][0] \rvert, \lvert \textit{startPos} - \textit{fruits}[j][0] \rvert)$ 大于 $k$ ，那么我们就将 $i$ 循环向右移动，直到 $i > j$ 或者区间内的最小步数小于等于 $k$ 。此时我们更新答案 $\textit{ans} = \max(\textit{ans}, s)$ 。继续移动 $j$ ，直到 $j$ 到达数组末尾。

最后返回答案即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        ans = i = s = 0
        for j, (pj, fj) in enumerate(fruits):
            s += fj
            while (
                i <= j
                and pj
                - fruits[i][0]
                + min(abs(startPos - fruits[i][0]), abs(startPos - fruits[j][0]))
                > k
            ):
                s -= fruits[i][1]
                i += 1
            ans = max(ans, s)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) due to scanning the fruits array once with sliding window and prefix sums. Space complexity is O(1) since only indices and totals are tracked, no additional arrays are required.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Focus on binary search to efficiently identify valid movement intervals.
question_mark
Watch for off-by-one errors when combining left-right movements within k steps.
question_mark
Consider prefix sums to avoid recomputing interval sums repeatedly.

warning

常见陷阱

外企场景

error
Forgetting that optimal paths may involve turning once; don't assume always moving in a single direction.
error
Exceeding k steps when summing intervals due to miscalculating distance between positions.
error
Recomputing fruit sums for every interval instead of using prefix sums, which slows the solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the movement cost per step or allow diagonal moves along the x-axis.
arrow_right_alt
Fruits can regenerate after harvesting, requiring multiple passes over positions.
arrow_right_alt
Positions may not be sorted, requiring initial sorting before sliding window application.

help

常见问题

外企场景

继续练习

#2271 毯子覆盖的最多白色砖块数 #2302 统计得分小于 K 的子数组数目 #1838 最高频元素的频数