首页算法

2106. 摘水果

难度困难

在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。 fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。

另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。

返回你可以摘到水果的 最大总数 。

示例 1：

img

输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4

输出：9

解释：

最佳路线为：

  • 向右移动到位置 6 ，摘到 3 个水果
  • 向右移动到位置 8 ，摘到 6 个水果

移动 3 步，共摘到 3 + 6 = 9 个水果

示例 2：

img

输入：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：

img

输入：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, startPos + k] 往右枚举 i

  • 向右走 i 步，再向左走 k - 2 * i 步

对区间 [startPos - k, startPos] 往左枚举 i

  • 向左走 i 步，在向右走 k - 2 * i 步
class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        // 区间范围的最大和
        int[] arr = new int[200001];
        int n = 0;
        for (int[] fruit : fruits) {
            arr[fruit[0]] = fruit[1];
            n = Math.max(fruit[0], n);
        }
        int[] s = new int[200002];
        for (int i = 0; i < 200001; i++) {
            s[i + 1] = s[i] + arr[i];
        }
        int ans = 0;
        int r = Math.min(n, startPos + k);
        int l = Math.max(0, startPos - k);
        // 向右走 i 步，在向左走 k - 2 * i 步
        for (int j = startPos; j <= r; j++) {
            // [i, j]
            int i = startPos - Math.max(k - 2 * (j - startPos), 0);
            i = Math.max(i, 0);
            ans = Math.max(ans, s[j + 1] - s[i]);
        }
        // 向左走 i 步，在向右走 k - 2 * i 步
        for (int i = startPos; i >= l; i--) {
            // [i, j]
            int j = startPos + Math.max(k - 2 * (startPos - i), 0);
            j = Math.min(n, j);
            ans = Math.max(ans, s[j + 1] - s[i]);
        }
        return ans;
    }
}

# 复杂度分析

  • 时间复杂度 ：O(n)O(n)

  • 空间复杂度 ：O(n)O(n)

# 滑动窗口 + 二分

枚举右端点 r ，不断缩小左端点直至满足要求的最大左端点

如何让 [l, r] 满足要求呢？

  • 先往左走 startPos - f[l][0] 步，再往右走 startPos - f[l][0] + f[r][0] - startPos

    startPos - f[l][0] + startPos - f[l][0] + f[r][0] - startPos <= k

  • 先往右走 f[r][0] - startPos 步，再往左走 f[r][0] - startPos + startPos - f[l][0]

    f[r][0] - startPos + f[r][0] - startPos + startPos - f[l][0] <= K

确定左边界可以采用二分查找 start - k

class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        // 滑动窗口，不直接计算
        int n = fruits.length;
        int s = 0;
        int ans = 0;
        int max = Math.min(startPos + k, fruits[n - 1][0]);
        // 左边界二分查找
        int l = binarySearch(fruits, startPos - k);
        int r = l;
        while (r < n && fruits[r][0] <= max) {
            s += fruits[r][1];
            // 不满足条件，不断缩小左边界
            while (startPos - fruits[l][0] + startPos - fruits[l][0] + fruits[r][0] - startPos > k
            && fruits[r][0] - startPos + fruits[r][0] - startPos + startPos - fruits[l][0] > k) {
                s -= fruits[l++][1];
            }
            ans = Math.max(ans, s);
            r++;
        }
        return ans;
    }
    // 返回大于等于 k 的最小值
    public int binarySearch(int[][] fruits, int k) {
        int l = 0;
        int r = fruits.length;
        while (l < r) {
            int m = (l + r) / 2;
            if (fruits[m][0] >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}
# 复杂度分析


    

  • 

    时间复杂度 ：O(n)O(n)
    

    • 

  • 

    空间复杂度 ：O(n)O(n)
    

    •