文章目錄
- 題目概要
- java 解法
- 詳解
題目概要
在一個無限的 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<=105fruits[i].length==20<=startPos,positioni<=2?105對于任意i>0，positioni?1<positioni均成立（下標從0開始計數）1<=amounti<=1040<=k<=2?1051 <= fruits.length <= 10^5 \\ fruits[i].length == 2\\ 0 <= startPos, positioni <= 2 * 10^5 \\ 對于任意 i > 0 ，positioni-1 < positioni 均成立（下標從 0 開始計數）\\ 1 <= amounti <= 10^4 \\ 0 <= k <= 2 * 10^5 1<=fruits.length<=105fruits[i].length==20<=startPos,positioni<=2?105對于任意i>0，positioni?1<positioni均成立（下標從0開始計數）1<=amounti<=1040<=k<=2?105
java 解法
public int maxTotalFruits(int[][] fruits, int startPos, int k) {int n = fruits.length;// 提取位置和數量，方便操作int[] positions = new int[n];int[] amounts = new int[n];for (int i = 0; i < n; i++) {positions[i] = fruits[i][0]; // 位置amounts[i] = fruits[i][1]; // 水果數量}// 前綴和數組：prefix[i] 表示前 i 個位置的水果總數int[] prefix = new int[n + 1];for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + amounts[i];}int maxFruits = 0; // 記錄能摘到的最大水果數int left = 0; // 滑動窗口的左指針// 滑動窗口：右指針 right 從 0 到 n-1for (int right = 0; right < n; right++) {// 當前嘗試的區間是 [left, right]int L = positions[left]; // 區間最左位置int R = positions[right]; // 區間最右位置// 計算從 startPos 出發，走完 [L, R] 所需的最少步數int steps = calculateSteps(startPos, L, R);// 如果步數超過了 k，說明走太遠了，需要縮小窗口（移動 left）while (left <= right && steps > k) {left++; // 縮小左邊界if (left > right) break;L = positions[left];R = positions[right];steps = calculateSteps(startPos, L, R);}// 如果當前窗口有效，更新最大水果數if (left <= right) {int total = prefix[right + 1] - prefix[left]; // [left, right] 的水果總數maxFruits = Math.max(maxFruits, total);}}return maxFruits;
}// 計算從 startPos 出發，走完區間 [L, R] 所需的最少步數
private int calculateSteps(int startPos, int L, int R) {if (R <= startPos) {// 所有水果都在起點或左邊：只向左走return startPos - L;} else if (L >= startPos) {// 所有水果都在起點或右邊：只向右走return R - startPos;} else {// 水果分布在起點兩側// 方案1：先向左走到 L，再向右走到 Rint goLeftFirst = (startPos - L) * 2 + (R - startPos);// 方案2：先向右走到 R，再向左走到 Lint goRightFirst = (R - startPos) * 2 + (startPos - L);// 返回兩種方案中步數更少的那個return Math.min(goLeftFirst, goRightFirst);}
}public static void main(String[] args) {Solution1 solution = new Solution1();// 示例 1int[][] fruits1 = {{2,8},{6,3},{8,6}};System.out.println(solution.maxTotalFruits(fruits1, 5, 4)); // 輸出: 9// 示例 2int[][] fruits2 = {{0,9},{4,1},{5,7},{6,2},{7,4},{10,9}};System.out.println(solution.maxTotalFruits(fruits2, 5, 4)); // 輸出: 14// 示例 3int[][] fruits3 = {{0,3},{6,4},{8,5}};System.out.println(solution.maxTotalFruits(fruits3, 3, 2)); // 輸出: 0
}
詳解
目的：將二維信息解耦為兩個一維數組，便于后續使用雙指針、二分查找等操作。
int n = fruits.length;// 提取位置和數量，方便操作
int[] positions = new int[n];
int[] amounts = new int[n];
for (int i = 0; i < n; i++) {positions[i] = fruits[i][0]; // 位置amounts[i] = fruits[i][1]; // 水果數量
}
前綴和（Prefix Sum）用來快速計算總和的一種方式
第 i+1 個累計值 = 第 i 個累計值 + 第 i 個位置的水果數
// 前綴和數組：prefix[i] 表示前 i 個位置的水果總數
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + amounts[i];
}
拿示例 1： 舉例
fruits = [[2,8], [6,3], [8,6]]
最終前綴和數組
prefix[i] | 含義 | 對應的水果 |
|---|---|---|
prefix[0] = 0 | 前 0 個位置的水果總數 | 什么都沒有 |
prefix[1] = 8 | 前 1 個位置的水果總數 | 位置 2：8 個 |
prefix[2] = 11 | 前 2 個位置的水果總數 | 位置 2+6：8+3=11 |
prefix[3] = 17 | 前 3 個位置的水果總數 | 位置 2+6+8：8+3+6=17 |
用前綴和快速算“某段區間的水果總數
🌰 例子 1：只摘位置 6 的水果（第 1 個位置）
- left = 1, right = 1
- 總數 = prefix[right+1] - prefix[left] = prefix[2] - prefix[1] = 11 - 8 = 3 ?
🌰 例子 2：摘位置 6 和 8 的水果（第 1 和第 2 個位置）
- left = 1, right = 2
- 總數 = prefix[3] - prefix[1] = 17 - 8 = 9 ?
也就是 3 + 6 = 9
🌰 例子 3：摘所有水果（第 0 到第 2 個位置）
- left = 0, right = 2
- 總數 = prefix[3] - prefix[0] = 17 - 0 = 17 ?
🌰 例子 4：只摘位置 2 的水果（第 0 個位置）
- left = 0, right = 0
- 總數 = prefix[1] - prefix[0] = 8 - 0 = 8
這在滑動窗口中特別有用，因為 right 每移動一次，都要算一次區間和。
從左向右，滑動窗口
我們要在最多走 k 步的前提下，從起點 startPos 出發，摘到最多的水果。
maxFruits：就像一個“最高分記錄”，通過 在 合理的 k 步條件下獲取的最多水果數
外層循環：右指針 right 不斷向右擴展
right 從 0 開始，一步步向右移動（0 → 1 → 2 → …）
每次 right 向右一格，就相當于我們想多摘一個位置的水果
for (int right = 0; right < n; right++) {
當前嘗試的區間 [left, right]
拿示例 1： 舉例
fruits = [[2,8], [6,3], [8,6]]
positions = [2, 6, 8]
那么 以下就會從
| right | left | 區間 | 步數 | 是否可達 | 水果數 | maxFruits |
|---|---|---|---|---|---|---|
| 0 | 0 | [2] | 3 | ? | 8 | 8 |
| 1 | 0 | [2,6] | 5 | ? → left=1 | - | - |
| 1 | [6] | 1 | ? | 3 | max(8,3)=8 | |
| 2 | 1 | [6,8] | 3 | ? | 9 | max(8,9)=9 |
int L = positions[left]; // 區間最左位置
int R = positions[right]; // 區間最右位置
計算區間區間步數
計算走完這個區間需要多少步
left <= right 縮小空間，保持空間合法性
steps > k 步數超過k步后，進入 while 調整左側空間，使步數減少，
while (left <= right && steps > k) 用while 發現 septs 直到 空間合法后跳出循環
// 計算從 startPos 出發，走完 [L, R] 所需的最少步數
int steps = calculateSteps(startPos, L, R);// 如果步數超過了 k，說明走太遠了，需要縮小窗口（移動 left）
while (left <= right && steps > k) {left++; // 縮小左邊界if (left > right) break;L = positions[left];R = positions[right];steps = calculateSteps(startPos, L, R);
}
校驗合法性，并更新水果數
prefix[right + 1] - prefix[left] 這邊用到了上面 所寫的 前綴和 計算累計數量， left 跟 right 是 對應的坐標點，由于前綴和 第一個坐標點為 0 所以需要加1
prefix[i] | 含義 | 對應的水果 |
|---|---|---|
prefix[0] = 0 | 前 0 個位置的水果總數 | 什么都沒有 |
prefix[1] = 8 | 前 1 個位置的水果總數 | 位置 2：8 個 |
prefix[2] = 11 | 前 2 個位置的水果總數 | 位置 2+6：8+3=11 |
prefix[3] = 17 | 前 3 個位置的水果總數 | 位置 2+6+8：8+3+6=17 |
right + 1 前 right+1 個數的總和
left 前 left 個數的總和
amounts: [ 8 , 3 , 6 ]↑ ↑ ↑
索引: 0 1 2prefix: [0, 8, 11, 17]↑ ↑ ↑ ↑0 1 2 3
繼續用示例1
fruits = [[2,8],[6,3],[8,6]]
比如 ：獲取 位置為6 的 水果， 由于 前綴和的緣故 第一個是固定值，后面的值是累加過來的
prefix[right + 1] - prefix[left] = prefix[2] - prefix[1] = 11 - 8 = 3
Math.max 對比 兩數大小
// 如果當前窗口有效，更新最大水果數
if (left <= right) {int total = prefix[right + 1] - prefix[left]; // [left, right] 的水果總數maxFruits = Math.max(maxFruits, total);
}
計算步數
R <= startPos 從步數左側走完的步數， 上面 for 循環 R 是在一步步從左走到右側的
L >= startPos 從右側走完的步數，L 因為上面空間縮小調整一步步走到右側
獲取 在 R 大于起始步數并 L 還沒移動到右側時 獲取 中間的兩種狀態
(startPos - L) * 2 + (R - startPos) 先向左走到 L，再向右走到 R
(R - startPos) * 2 + (startPos - L) 先先向右走到 R，再向左走到 L
Math.min 獲取兩者最小步數方案，可能起始位置并不居中，導致 往回走步數減少減少的情況
// 計算從 startPos 出發，走完區間 [L, R] 所需的最少步數
private int calculateSteps(int startPos, int L, int R) {if (R <= startPos) {// 所有水果都在起點或左邊：只向左走return startPos - L;} else if (L >= startPos) {// 所有水果都在起點或右邊：只向右走return R - startPos;} else {// 水果分布在起點兩側// 方案1：先向左走到 L，再向右走到 Rint goLeftFirst = (startPos - L) * 2 + (R - startPos);// 方案2：先向右走到 R，再向左走到 Lint goRightFirst = (R - startPos) * 2 + (startPos - L);// 返回兩種方案中步數更少的那個return Math.min(goLeftFirst, goRightFirst);}
}
