摘水果【LC2106】
在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni,amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。返回你可以摘到水果的 最大总数 。
没有想到用双指针，用前缀和数组做的
前缀和数组
思路
- 为了摘到最多的水果，我们一定不能来回重复走，因此一定是向某个方向一直走，有多余的步数才向另一个方向走。
- 假设向左走了i步，那么向右最多走k−2∗i，可以采摘的区间为[startPos−i,startPos+k−2∗i]
- 假设向右走了i步，那么向左最多走k−2∗i，可以采摘的区间为[startPos−k+2∗i,startPos+i]
注意：移动时需要注意判断边界，如果要向两个方向都移动，那么向某个方向移动的距离i必须小于等于k/2
- 因此可以使用前缀和数组统计每个位置采摘到的水果，快速计算某个区间可以采摘到的水果
- 实现
class Solution { public int maxTotalFruits(int[][] fruits, int startPos, int k) { // 前缀和 // 枚举可能的区间 // [startPos - i, startPos + k - 2 * i] [startPos - k + 2 * i, startPos + i] int n = fruits.length; int maxPos = Math.max(fruits[n - 1][0], startPos); int[] num = new int[maxPos + 1]; int[] preSum = new int[maxPos + 2]; for (int[] fruit : fruits){ num[fruit[0]] = fruit[1]; } for (int i = 0; i <= maxPos; i++){ preSum[i + 1] = preSum[i] + num[i]; } // 向一个方向走 int res = Math.max(preSum[Math.min(startPos + k + 1, maxPos + 1)] - preSum[startPos], preSum[startPos + 1] - preSum[Math.max(0, startPos - k)]); for (int i = 0; i <= k / 2; i++){ // 往左走i步(最远走到0)，往右最多走k - 2 * i步 res = Math.max(preSum[Math.min(startPos + k - 2 * i + 1, maxPos + 1)] - preSum[Math.max(startPos - i, 0)], res); // 往右走i步（最远走到maxPos），往左最多走k - 2 * i步 res = Math.max(preSum[Math.min(startPos + i + 1, maxPos + 1)] - preSum[Math.max(startPos - k + 2 * i, 0)], res); } return res; } }
复杂度
- 时间复杂度：O(maxPos)，maxPos为最远的有水果的位置和起点位置的最大值
- 空间复杂度：O(maxPos)
滑动窗口+二分
- 思路
使用滑动窗口维护可以摘到的区间[l,r] - 首先找到最小的满足fruits[l][0]≥startPos−k的有水果的位置left【枚举或者二分】，那么初始区间为[left,startPos]
- 然后右移右指针r，满足fruits[r][0]≤startPos+k，移动左指针l至可以采摘到为止，只要以下式子有一个满足条件，那么区间[l,r]内的水果均可以采摘到
- 实现
class Solution { public int maxTotalFruits(int[][] fruits, int startPos, int k) { int left = lowerBound(fruits, startPos - k); // 向左最远能到 fruits[left][0] int right = left, s = 0, n = fruits.length; for (; right < n && fruits[right][0] <= startPos; right++) s += fruits[right][1]; // 从 fruits[left][0] 到 startPos 的水果数 int ans = s; for (; right < n && fruits[right][0] <= startPos + k; right++) { s += fruits[right][1]; // 枚举最右位置为 fruits[right][0] while (fruits[right][0] * 2 - fruits[left][0] - startPos > k && fruits[right][0] - fruits[left][0] * 2 + startPos > k) s -= fruits[left++][1]; // fruits[left][0] 无法到达 ans = Math.max(ans, s); // 更新答案最大值 } return ans; } // 见 https://www.bilibili.com/video/BV1AP41137w7/ private int lowerBound(int[][] fruits, int target) { int left = -1, right = fruits.length; // 开区间 (left, right) while (left + 1 < right) { // 开区间不为空 // 循环不变量： // fruits[left][0] < target // fruits[right][0] >= target int mid = (left + right) >>> 1; if (fruits[mid][0] < target) left = mid; // 范围缩小到 (mid, right) else right = mid; // 范围缩小到 (left, mid) } return right; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/solutions/2254860/hua-dong-chuang-kou-jian-ji-xie-fa-pytho-1c2d/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(n)，n为
fruits的长度 - 空间复杂度：O(1)
