摘水果

2106. 摘水果

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

另给你两个整数 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 <= 10⁵
fruits[i].length == 2
0 <= startPos, position_i <= 2 * 10⁵
对于任意 i > 0 ，position_i-1 < position_i 均成立（下标从 0 开始计数）
1 <= amount_i <= 10⁴
0 <= k <= 2 * 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) { } };

golang 解法, 执行用时: 216 ms, 内存消耗: 19.4 MB, 提交时间: 2023-05-05 15:47:15

func maxTotalFruits(fruits [][]int, startPos, k int) (ans int) {
    n := len(fruits)
    // 向左最远能到 fruits[left][0]
    left := sort.Search(n, func(i int) bool { return fruits[i][0] >= startPos-k })
    for right, s := left, 0; right < n && fruits[right][0] <= startPos+k; right++ {
        s += fruits[right][1] // 枚举最右位置为 fruits[right][0]
        for 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] 无法到达
            left++
        }
        ans = max(ans, s) // 更新答案最大值
    }
    return
}

func max(a, b int) int { if a < b { return b }; return a }

java 解法, 执行用时: 2 ms, 内存消耗: 94.6 MB, 提交时间: 2023-05-05 15:47:03

class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int left = lowerBound(fruits, startPos - k); // 向左最远能到 fruits[left][0]
        int ans = 0, s = 0, n = fruits.length;
        for (int right = left; 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;
    }
}

python3 解法, 执行用时: 228 ms, 内存消耗: 50.2 MB, 提交时间: 2023-05-05 15:46:51

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]
        ans = s = 0
        for pos, amount in fruits[left:]:
            if pos > startPos + k: break
            s += amount
            while pos * 2 - fruits[left][0] - startPos > k and \
                  pos - fruits[left][0] * 2 + startPos > k:
                s -= fruits[left][1]  # fruits[left][0] 无法到达
                left += 1
            ans = max(ans, s)  # 更新答案最大值
        return ans

上一题

下一题

详情