摘水果
难度:
标签:
题目描述
在一个无限的 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 * 105
代码结果
运行时间: 124 ms, 内存: 49.3 MB
// 思路：利用Java Stream API实现同样的逻辑。我们依然使用双指针方法，
// 通过遍历fruits数组并通过Stream API的处理来计算最大水果数量。
import java.util.stream.IntStream;
public class SolutionStream {
public int maxFruits(int[][] fruits, int startPos, int k) {
int maxFruits = 0;
int left = 0, right = 0;
int n = fruits.length;
int currentFruits = 0;
// 使用IntStream模拟向右移动
maxFruits = IntStream.range(0, n)
.takeWhile(i -> fruits[i][0] <= startPos + k)
.map(i -> fruits[i][1])
.sum();
currentFruits = maxFruits;
// 向左移动的过程中更新最大水果数量
for (; left < n && fruits[left][0] <= startPos; left++) {
currentFruits -= fruits[left][1];
int additionalFruits = IntStream.range(right, n)
.takeWhile(i -> fruits[i][0] <= startPos + k - (fruits[left][0] - startPos) * 2)
.map(i -> fruits[i][1])
.sum();
maxFruits = Math.max(maxFruits, currentFruits + additionalFruits);
right = IntStream.range(right, n)
.takeWhile(i -> fruits[i][0] <= startPos + k - (fruits[left][0] - startPos) * 2)
.max().orElse(right);
}
return maxFruits;
}
}
解释
方法:
此题解采用滑动窗口与二分搜索的结合方法，以最大化在给定步数内摘到的水果总数。首先，使用两次二分搜索确定起始位置左右的水果范围，即可能达到的左边界和右边界。随后，通过滑动窗口遍历这个范围，尝试不同的路径组合（先左后右或者先右后左），计算在不超过k步的条件下可以摘到的最大水果数。每次移动窗口时，更新当前窗口内的水果总数，并与之前的最大值进行比较，以保留可能的最大收获。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在使用二分搜索确定起始位置左右的水果范围时，你是如何确保这些范围内的水果都可以在k步内被摘到的？
▷🦆
你提到在滑动窗口中尝试不同的路径组合（先左后右或者先右后左），但代码示例中似乎只展示了一种方向的处理，如何处理另一种方向？
▷🦆
在更新滑动窗口时，你如何确保即使移动窗口左边界也不会错过可能的最大收获？
▷🦆
代码中使用了`bisect_left(fruits, [startPos+1])`来找到右侧水果的起始位置，为什么选择`startPos+1`作为开始而不是`startPos`？
▷