企业官网建设流程全解析

我来帮你解决 LeetCode 2106. 摘水果这道题。让我先搜索一下这道题的详细信息和最优解法。
这道题是 LeetCode 2106. 摘水果（Maximum Fruits Harvested After at Most K Steps），难度为 Hard。我来为你详细讲解最优解法。

问题理解

- 在 x 轴上有若干水果，每个位置 `positioni` 有 `amounti` 个水果
- 你从 `startPos` 出发，最多走 `k` 步（每移动一个单位算一步）
- 到达某个位置会摘走该位置全部水果，水果不会再生
- 求最多能摘多少水果

关键观察：最优策略一定是先往一个方向走，然后掉头往另一个方向走（或者只往一个方向走）。不会来回折返。

最优解法：滑动窗口 O(n)

这是灵茶山艾府推荐的简洁写法 ，时间复杂度 O(n)，空间复杂度 O(1)。

核心思路

用滑动窗口 `[left, right]` 表示当前考虑采摘的水果区间，窗口内的水果必须能在 `k` 步内全部摘到。

计算从 startPos 出发，摘完 [left, right] 区间内所有水果所需的最少步数：

```
step = (fruits[right][0] - fruits[left][0]) // 区间长度
+ min(|startPos - fruits[left][0]|, // 从起点到较近端点的距离
|startPos - fruits[right][0]|)
```

解释：先走到离起点较近的那个端点，然后横穿整个区间到另一个端点。

Java 代码

```java
class Solution {
public int maxTotalFruits(int[][] fruits, int startPos, int k) {
int ans = 0, sum = 0;
int left = 0;

for (int right = 0; right < fruits.length; right++) {
sum += fruits[right][1]; // 右端点加入窗口

// 当窗口不合法时，收缩左端点
// 不合法条件：摘完[left, right]需要超过k步
while (left <= right &&
fruits[right][0] - fruits[left][0] +
Math.min(Math.abs(startPos - fruits[left][0]),
Math.abs(startPos - fruits[right][0])) > k) {
sum -= fruits[left][1];
left++;
}

ans = Math.max(ans, sum);
}

return ans;
}
}
```

另一种更直观的写法

```java
class Solution {
public int maxTotalFruits(int[][] fruits, int startPos, int k) {
int ans = 0, sum = 0;
for (int l = 0, r = 0; r < fruits.length; ++r) {
sum += fruits[r][1];
while (l <= r && !check(fruits[l][0], fruits[r][0], startPos, k)) {
sum -= fruits[l++][1];
}
ans = Math.max(ans, sum);
}
return ans;
}

// 检查窗口 [a, b] 是否能在 k 步内完成
public boolean check(int a, int b, int x, int k) {
if (a <= x && b <= x) return x - a <= k; // 都在左边
if (a >= x && b >= x) return b - x <= k; // 都在右边
// a在左边，b在右边（或反之）
int leftDist = x - a;
int rightDist = b - x;
return Math.min(leftDist, rightDist) * 2 + Math.max(leftDist, rightDist) <= k;
}
}
```

其他解法对比

解法 时间复杂度 空间复杂度 特点
滑动窗口 O(n) O(1) 最优，代码简洁
前缀和 + 二分 O(n log n) O(n) 思路直观，容易理解
枚举方向 + 前缀和 O(n + k) O(n) 需要坐标范围不大

为什么滑动窗口有效？

关键性质：当 right 固定时，如果 `[left, right]` 不合法，那么 `[left-1, right]` 也一定不合法（步数不会减少只会增加或不变）。因此可以用双指针，left 只会向右移动，不会回退，保证 O(n) 复杂度。

示例验证

示例 1：`fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4`

- 窗口 `[1,2]`（位置 6 和 8）：步数 = `(8-6) + min(|5-6|, |5-8|) = 2 + 1 = 3 ≤ 4`，水果数 = 3+6 = 9 ✓

示例 2：`fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4`

- 窗口 `[1,4]`（位置 4,5,6,7）：步数 = `(7-4) + min(|5-4|, |5-7|) = 3 + 1 = 4 ≤ 4`，水果数 = 1+7+2+4 = 14 ✓

滑动窗口解法是最推荐的做法，时间 O(n)、空间 O(1)，面试中非常高效。㇏