2106. 在至多 K 步后收集的最大水果数

Hard

题目描述

在一个无限的 x 轴上，有一些位置上有水果。给定一个二维整数数组 fruits，其中 fruits[i] = [positioni, amounti] 表示在位置 positioni 上有 amounti 个水果。数组 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 <= 10^5
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 10^5
positioni-1 < positioni 对于任意 i > 0 (0-indexed)
1 <= amounti <= 10^4
0 <= k <= 2 * 10^5

解题思路

这道题的关键洞察是最优路径最多转向一次。也就是说，最优路径只有四种模式：

只向左走
只向右走
先向左走，再向右走
先向右走，再向左走

对于模式3和4，我们可以枚举向一个方向走的步数，然后计算剩余步数能向另一个方向走多远。

解法思路：

预处理：为了快速计算任意区间的水果总数，我们需要构建位置和水果数量的映射，以及前缀和数组。
枚举所有可能路径：
- 只向左走：从起始位置向左最多走k步
- 只向右走：从起始位置向右最多走k步
- 先左后右：枚举向左走的步数left（0到k），剩余步数k-left用于向右走
- 先右后左：枚举向右走的步数right（0到k），剩余步数k-right用于向左走
优化计算：使用前缀和快速计算任意区间的水果总数，使用二分查找快速定位位置范围。
边界处理：注意处理起始位置本身的水果，以及确保不会重复计算。

这种方法的时间复杂度是O(k)，因为我们枚举了所有可能的步数分配方案。

代码实现

class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int n = fruits.size();
        vector<int> positions, amounts;
        
        for (auto& fruit : fruits) {
            positions.push_back(fruit[0]);
            amounts.push_back(fruit[1]);
        }
        
        auto getFruits = [&](int left, int right) {
            if (left > right) return 0;
            int l = lower_bound(positions.begin(), positions.end(), left) - positions.begin();
            int r = upper_bound(positions.begin(), positions.end(), right) - positions.begin() - 1;
            if (l > r) return 0;
            
            int sum = 0;
            for (int i = l; i <= r; i++) {
                sum += amounts[i];
            }
            return sum;
        };
        
        int maxFruits = 0;
        
        // 只向左走
        maxFruits = max(maxFruits, getFruits(startPos - k, startPos));
        
        // 只向右走
        maxFruits = max(maxFruits, getFruits(startPos, startPos + k));
        
        // 先向左走left步，再向右走
        for (int left = 1; left <= k; left++) {
            int remaining = k - left;
            if (remaining >= left) {
                int leftPos = startPos - left;
                int rightPos = startPos + remaining - left;
                maxFruits = max(maxFruits, getFruits(leftPos, rightPos));
            }
        }
        
        // 先向右走right步，再向左走
        for (int right = 1; right <= k; right++) {
            int remaining = k - right;
            if (remaining >= right) {
                int rightPos = startPos + right;
                int leftPos = startPos - (remaining - right);
                maxFruits = max(maxFruits, getFruits(leftPos, rightPos));
            }
        }
        
        return maxFruits;
    }
};

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        positions = [fruit[0] for fruit in fruits]
        amounts = [fruit[1] for fruit in fruits]
        
        def get_fruits(left, right):
            if left > right:
                return 0
            
            l = bisect.bisect_left(positions, left)
            r = bisect.bisect_right(positions, right) - 1
            
            if l > r:
                return 0
            
            return sum(amounts[l:r+1])
        
        max_fruits = 0
        
        # 只向左走
        max_fruits = max(max_fruits, get_fruits(startPos - k, startPos))
        
        # 只向右走
        max_fruits = max(max_fruits, get_fruits(startPos, startPos + k))
        
        # 先向左走left步，再向右走
        for left in range(1, k + 1):
            remaining = k - left
            if remaining >= left:
                left_pos = startPos - left
                right_pos = startPos + remaining - left
                max_fruits = max(max_fruits, get_fruits(left_pos, right_pos))
        
        # 先向右走right步，再向左走
        for right in range(1, k + 1):
            remaining = k - right
            if remaining >= right:
                right_pos = startPos + right
                left_pos = startPos - (remaining - right)
                max_fruits = max(max_fruits, get_fruits(left_pos, right_pos))
        
        return max_fruits

public class Solution {
    public int MaxTotalFruits(int[][] fruits, int startPos, int k) {
        var positions = fruits.Select(f => f[0]).ToArray();
        var amounts = fruits.Select(f => f[1]).ToArray();
        
        int GetFruits(int left, int right) {
            if (left > right) return 0;
            
            int l = Array.BinarySearch(positions, left);
            if (l < 0) l = ~l;
            
            int r = Array.BinarySearch(positions, right);
            if (r < 0) r = ~r - 1;
            else r = Array.FindLastIndex(positions, x => x == right);
            
            if (l > r) return 0;
            
            int sum = 0;
            for (int i = l; i <= r; i++) {
                sum += amounts[i];
            }
            return sum;
        }
        
        int maxFruits = 0;
        
        // 只向左走
        maxFruits = Math.Max(maxFruits, GetFruits(startPos - k, startPos));
        
        // 只向右走
        maxFruits = Math.Max(maxFruits, GetFruits(startPos, startPos + k));
        
        // 先向左走left步，再向右走
        for (int left = 1; left <= k; left++) {
            int remaining = k - left;
            if (remaining >= left) {
                int leftPos = startPos - left;
                int rightPos = startPos + remaining - left;
                maxFruits = Math.Max(maxFruits, GetFruits(leftPos, rightPos));
            }
        }
        
        // 先向右走right步，再向左走
        for (int right = 1; right <= k; right++) {
            int remaining = k - right;
            if (remaining >= right) {
                int rightPos = startPos + right;
                int leftPos = startPos - (remaining - right);
                maxFruits = Math.Max(maxFruits, GetFruits(leftPos, rightPos));
            }
        }
        
        return maxFruits;
    }
}

var maxTotalFruits = function(fruits, startPos, k) {
    const positions = fruits.map(fruit => fruit[0]);
    const amounts = fruits.map(fruit => fruit[1]);
    
    function binarySearchLeft(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    
    function binarySearchRight(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left - 1;
    }
    
    function getFruits(left, right) {
        if (left > right) return 0;
        
        const l = binarySearchLeft(positions, left);
        const r = binarySearchRight(positions, right);
        
        if (l > r) return 0;
        
        let sum = 0;
        for (let i = l; i <= r; i++) {
            sum += amounts[i];
        }
        return sum;
    }
    
    let maxFruits = 0;
    
    // 只向左走
    maxFruits = Math.max(maxFruits, getFruits(startPos - k, startPos));
    
    // 只向右走
    maxFruits = Math.max(maxFruits, getFruits(startPos, startPos + k));
    
    // 先向左走left步，再向右走
    for (let left = 1; left <= k; left++) {
        const remaining = k - left;
        if (remaining >= left) {
            const leftPos = startPos - left;
            const rightPos = startPos + remaining - left;
            maxFruits = Math.max(maxFruits, getFruits(leftPos, rightPos));
        }
    }
    
    // 先向右走right步，再向左走
    for (let right = 1; right <= k; right++) {
        const remaining = k - right;
        if (remaining >= right) {
            const rightPos = startPos + right;
            const leftPos = startPos - (remaining - right);
            maxFruits = Math.max(maxFruits, getFruits(leftPos, rightPos));
        }
    }
    
    return maxFruits;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(k × n)
空间复杂度	O(1)

注：其中 k 是最大步数，n 是水果数组的长度。时间复杂度主要来自于枚举所有可能的步数分配（O(k)）和每次计算区间水果总数（O(n)）。可以通过前缀和优化为 O(k × log n)。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目