Hard

题目描述

你有 k 个包。给你一个下标从 0 开始的整数数组 weights，其中 weights[i] 是第 i 个弹珠的重量。同时给你整数 k。

请你按照下述规则将弹珠放进 k 个包中：

  • 没有包是空的。
  • 如果第 i 个弹珠和第 j 个弹珠在同一个包中，那么下标在 i 和 j 之间的所有弹珠都必须在同一个包中。
  • 如果一个包中包含下标从 i 到 j（含 i 和 j）的所有弹珠，那么这个包的开销是 weights[i] + weights[j]。

分配弹珠后的 分数 是所有 k 个包的开销之和。

返回所有可能的弹珠分配中 最高分数 和 最低分数 的 差值。

示例 1：

输入：weights = [1,3,5,1], k = 2
输出：4
解释：
分配 [1],[3,5,1] 产生最小分数 (1+1) + (3+1) = 6。
分配 [1,3],[5,1] 产生最大分数 (1+3) + (5+1) = 10。
因此，返回它们的差值 10 - 6 = 4。

示例 2：

输入：weights = [1, 3], k = 2
输出：0
解释：唯一可能的分配是 [1],[3]。
由于最大和最小分数相同，我们返回 0。

提示：

  • 1 <= k <= weights.length <= 10^5
  • 1 <= weights[i] <= 10^9

解题思路

解题思路

这道题的关键洞察是：每个包的开销只取决于包的第一个和最后一个弹珠的重量。因此我们需要选择 k-1 个分割点来将数组分成 k 个连续子数组。

首先分析分数的组成：

  • 无论怎么分割，第一个弹珠 weights[0] 和最后一个弹珠 weights[n-1] 总会被计算一次
  • 对于中间的分割点，如果在位置 i 和 i+1 之间分割，会额外贡献 weights[i] + weights[i+1] 的开销

所以问题转化为：从所有可能的相邻元素对 weights[i] + weights[i+1]（其中 0 ≤ i < n-1）中选择 k-1 个，使得总和最大或最小。

算法步骤：

  1. 计算所有相邻元素对的和：pairs[i] = weights[i] + weights[i+1]
  2. 对 pairs 数组排序
  3. 最小分数：选择最小的 k-1 个对
  4. 最大分数：选择最大的 k-1 个对
  5. 返回两者差值

时间复杂度主要由排序决定，为 O(n log n)。这种方法比使用堆的方法更简洁高效。

代码实现

class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        int n = weights.size();
        if (k == 1 || k == n) return 0;
        
        vector<long long> pairs;
        for (int i = 0; i < n - 1; i++) {
            pairs.push_back(weights[i] + weights[i + 1]);
        }
        
        sort(pairs.begin(), pairs.end());
        
        long long minScore = 0, maxScore = 0;
        for (int i = 0; i < k - 1; i++) {
            minScore += pairs[i];
            maxScore += pairs[pairs.size() - 1 - i];
        }
        
        return maxScore - minScore;
    }
};

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        n = len(weights)
        if k == 1 or k == n:
            return 0
        
        pairs = []
        for i in range(n - 1):
            pairs.append(weights[i] + weights[i + 1])
        
        pairs.sort()
        
        min_score = sum(pairs[:k-1])
        max_score = sum(pairs[-(k-1):])
        
        return max_score - min_score

public class Solution {
    public long PutMarbles(int[] weights, int k) {
        int n = weights.Length;
        if (k == 1 || k == n) return 0;
        
        long[] pairs = new long[n - 1];
        for (int i = 0; i < n - 1; i++) {
            pairs[i] = weights[i] + weights[i + 1];
        }
        
        Array.Sort(pairs);
        
        long minScore = 0, maxScore = 0;
        for (int i = 0; i < k - 1; i++) {
            minScore += pairs[i];
            maxScore += pairs[pairs.Length - 1 - i];
        }
        
        return maxScore - minScore;
    }
}

/**
 * @param {number[]} weights
 * @param {number} k
 * @return {number}
 */
var putMarbles = function(weights, k) {
    const n = weights.length;
    if (k === 1 || k === n) return 0;
    
    const pairSums = [];
    for (let i = 0; i < n - 1; i++) {
        pairSums.push(weights[i] + weights[i + 1]);
    }
    
    pairSums.sort((a, b) => a - b);
    
    let minScore = weights[0] + weights[n - 1];
    let maxScore = weights[0] + weights[n - 1];
    
    for (let i = 0; i < k - 1; i++) {
        minScore += pairSums[i];
        maxScore += pairSums[n - 2 - i];
    }
    
    return maxScore - minScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在对相邻元素对数组的排序
空间复杂度O(n)存储相邻元素对数组