Medium

题目描述

在数轴上有无限个袋子，每个坐标位置一个袋子。其中一些袋子包含硬币。

给你一个二维数组 coins，其中 coins[i] = [li, ri, ci] 表示从 li 到 ri 的每个袋子都包含 ci 个硬币。

包含硬币的区间是不重叠的。

同时给你一个整数 k。

返回通过收集 k 个连续袋子能获得的最多硬币数量。

示例 1：

输入：coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4
输出：10
解释：选择位置 [3, 4, 5, 6] 的袋子可以获得最多硬币：2 + 0 + 4 + 4 = 10。

示例 2：

输入：coins = [[1,10,3]], k = 2
输出：6
解释：选择位置 [1, 2] 的袋子可以获得最多硬币：3 + 3 = 6。

约束条件：

  • 1 <= coins.length <= 10^5
  • 1 <= k <= 10^9
  • coins[i] == [li, ri, ci]
  • 1 <= li <= ri <= 10^9
  • 1 <= ci <= 1000
  • 给定的区间不重叠

提示：

  • k个连续袋子的最优起始位置要么是某个 li，要么是某个 ri - k + 1。

解题思路

这道题的关键在于理解最优起始位置的特性。根据提示，k个连续袋子的最优起始位置只可能是某个区间的左端点 li 或者某个区间的右端点减去k再加1，即 ri - k + 1。

思路分析：

  1. 候选起始位置：我们需要考虑所有可能的起始位置。由于区间不重叠，最优解的起始位置必然是某个区间的边界点附近。具体来说，起始位置只可能是：

    • 某个区间的左端点 li
    • 某个区间的右端点向左偏移k-1个位置，即 ri - k + 1

  2. 计算每个起始位置的硬币数：对于每个候选起始位置，我们需要计算从该位置开始的k个连续袋子能获得多少硬币。这需要找到与区间 [start, start + k - 1] 相交的所有硬币区间。

  3. 优化计算：可以先对所有硬币区间按左端点排序，然后对每个起始位置使用二分查找找到第一个可能相交的区间，再向后遍历计算总硬币数。

  4. 处理区间相交：当计算区间 [start, start + k - 1] 与硬币区间 [li, ri] 的相交部分时，相交长度为 min(ri, start + k - 1) - max(li, start) + 1，硬币数为相交长度乘以该区间的硬币密度。

推荐解法：使用排序 + 二分查找的方法，时间复杂度相对较优。

代码实现

class Solution {
public:
    long long maximumCoins(vector<vector<int>>& coins, int k) {
        sort(coins.begin(), coins.end());
        
        set<long long> candidates;
        for (auto& coin : coins) {
            candidates.insert(coin[0]);
            candidates.insert(max(1LL, (long long)coin[1] - k + 1));
        }
        
        long long maxCoins = 0;
        
        for (long long start : candidates) {
            long long end = start + k - 1;
            long long currentCoins = 0;
            
            for (auto& coin : coins) {
                long long left = coin[0], right = coin[1], value = coin[2];
                if (right < start || left > end) continue;
                
                long long overlapStart = max(left, start);
                long long overlapEnd = min(right, end);
                currentCoins += (overlapEnd - overlapStart + 1) * value;
            }
            
            maxCoins = max(maxCoins, currentCoins);
        }
        
        return maxCoins;
    }
};

class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        coins.sort()
        
        candidates = set()
        for left, right, _ in coins:
            candidates.add(left)
            candidates.add(max(1, right - k + 1))
        
        max_coins = 0
        
        for start in candidates:
            end = start + k - 1
            current_coins = 0
            
            for left, right, value in coins:
                if right < start or left > end:
                    continue
                
                overlap_start = max(left, start)
                overlap_end = min(right, end)
                current_coins += (overlap_end - overlap_start + 1) * value
            
            max_coins = max(max_coins, current_coins)
        
        return max_coins

public class Solution {
    public long MaximumCoins(int[][] coins, int k) {
        Array.Sort(coins, (a, b) => a[0].CompareTo(b[0]));
        
        var candidates = new HashSet<long>();
        foreach (var coin in coins) {
            candidates.Add(coin[0]);
            candidates.Add(Math.Max(1, (long)coin[1] - k + 1));
        }
        
        long maxCoins = 0;
        
        foreach (long start in candidates) {
            long end = start + k - 1;
            long currentCoins = 0;
            
            foreach (var coin in coins) {
                long left = coin[0], right = coin[1], value = coin[2];
                if (right < start || left > end) continue;
                
                long overlapStart = Math.Max(left, start);
                long overlapEnd = Math.Min(right, end);
                currentCoins += (overlapEnd - overlapStart + 1) * value;
            }
            
            maxCoins = Math.Max(maxCoins, currentCoins);
        }
        
        return maxCoins;
    }
}

var maximumCoins = function(coins, k) {
    coins.sort((a, b) => a[0] - b[0]);
    
    const candidates = new Set();
    for (const coin of coins) {
        candidates.add(coin[0]);
        candidates.add(Math.max(1, coin[1] - k + 1));
    }
    
    let maxCoins = 0;
    
    for (const start of candidates) {
        const end = start + k - 1;
        let currentCoins = 0;
        
        for (const coin of coins) {
            const [left, right, value] = coin;
            if (right < start || left > end) continue;
            
            const overlapStart = Math.max(left, start);
            const overlapEnd = Math.min(right, end);
            currentCoins += (overlapEnd - overlapStart + 1) * value;
        }
        
        maxCoins = Math.max(maxCoins, currentCoins);
    }
    
    return maxCoins;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n² log n)
空间复杂度O(n)

说明：

  • 时间复杂度：排序需要 O(n log n)，候选位置最多有 2n 个，对每个候选位置需要遍历所有区间计算重叠，总体为 O(n²)
  • 空间复杂度：需要存储候选位置的集合，最多 2n 个元素