題目

題目鏈接🔗

在一個無限的 x 坐標軸上，有許多水果分布在其中某些位置。給你一個二維整數數組 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 個水果放置在 positioni 上。fruits 已經按 positioni 升序排列 ，每個 positioni 互不相同 。

另給你兩個整數 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 <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
對于任意 i > 0 ，positioni-1 < positioni 均成立（下標從 0 開始計數）
1 <= amounti <= 104
0 <= k <= 2 * 105

思路

本題的核心是求解從起始位置startPos出發，最多走k步所能摘到的最大水果數量。考慮到路徑可能涉及向左或向右先走然后折返，我們可以枚舉可能的右側最遠位置R（從startPos到startPos + k的范圍），計算對應步數sr = R - startPos，然后計算在剩余步數下能到達的最左側距離dd。dd通過兩種策略計算：先向左走然后向右到R（dd <= (k - sr)/2），或先向右到R然后向左（dd <= k - 2*sr），取兩種策略的最大dd，并clamp到[0, startPos]。使用數組arr存儲每個位置的水果數量，left數組預計算從startPos向左的累加和。最后，對于每個R，計算從startPos - dd到R的水果總量，取最大值。這種方法高效地覆蓋了所有可能路徑，并確保在O(N)時間內求解，其中N = max(startPos, 最大位置) <= 4e5。

代碼

C++

class Solution {
public:int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {int n = max(startPos, fruits.back()[0]);vector<int> arr(n + 1, 0);for(auto& x : fruits) arr[x[0]] += x[1];vector<int> left(n + 1, 0);// 向左走 startPos - i 步int last = 0;for(int i = startPos; i >= 0; i --) {left[startPos - i] = last + arr[i];last = left[startPos - i];}int x = 0, res = 0;for(int i = startPos; i <= min(startPos + k, n); i ++) {if(i != startPos) x += arr[i];int sr = i - startPos; // 向右走了 sr 步// 最多向左走了幾步// l -> r// (k-sr)/2// r -> l// k - 2 * srres = max(res, x + left[min(startPos, max((k-sr)/2, k-2*sr))]);}return res;}
};

Java

class Solution {public int maxTotalFruits(int[][] fruits, int startPos, int k) {int n = Math.max(startPos, fruits[fruits.length - 1][0]);int[] arr = new int[n + 1];for (int[] x : fruits) {arr[x[0]] += x[1];}int[] left = new int[n + 1];int last = 0;for (int i = startPos; i >= 0; i--) {left[startPos - i] = last + arr[i];last = left[startPos - i];}int x = 0;int res = 0;int maxI = Math.min(startPos + k, n);for (int i = startPos; i <= maxI; i++) {if (i != startPos) {x += arr[i];}int sr = i - startPos;int cand1 = (k - sr) / 2;int cand2 = k - 2 * sr;int dd = Math.max(cand1, cand2);dd = Math.min(startPos, Math.max(0, dd));res = Math.max(res, x + left[dd]);}return res;}
}

Python

class Solution:def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:n = max(startPos, fruits[-1][0])arr = [0] * (n + 1)for p, a in fruits:arr[p] += aleft = [0] * (n + 1)last = 0for i in range(startPos, -1, -1):left[startPos - i] = last + arr[i]last = left[startPos - i]x = 0res = 0max_i = min(startPos + k, n)for i in range(startPos, max_i + 1):if i != startPos:x += arr[i]sr = i - startPoscand1 = (k - sr) // 2cand2 = k - 2 * srdd = max(cand1, cand2)dd = min(startPos, max(0, dd))res = max(res, x + left[dd])return res

復雜度分析

時間復雜度

O(N)，其中N = max(startPos, 最大位置) <= 4 \times 10^5，預計算left數組和循環枚舉右側位置均為O(N)。

空間復雜度

O(N)，用于存儲arr和left數組。

結果

該解法通過了LeetCode的所有測試用例，運行時間和內存消耗均在可接受范圍內。

總結

通過枚舉右側最遠位置并計算最大左側延伸距離，該方法巧妙地處理了路徑折返的兩種策略，確保了正確性和高效性。如果位置范圍較大，可考慮使用前綴和優化進一步壓縮空間，但當前實現已足夠優秀。https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/description/?envType=daily-question&envId=2025-08-03