K2.6快速 LeetCode 2106.摘水果 public int maxTotalFruits(int[][] fruits, int startPos, int k)
我来帮你解决 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)，面试中非常高效。㇏