跳至主要內容

2551. 将珠子放入背包中

2551. 将珠子放入背包中

🔴   🔖  贪心 数组 排序 堆（优先队列）  🔗 力扣open in new window LeetCodeopen in new window

题目

You have k bags. You are given a 0-indexed integer array weights where weights[i] is the weight of the ith marble. You are also given the integer k.

Divide the marbles into the k bags according to the following rules:

  • No bag is empty.
  • If the ith marble and jth marble are in a bag, then all marbles with an index between the ith and jth indices should also be in that same bag.
  • If a bag consists of all the marbles with an index from i to j inclusively, then the cost of the bag is weights[i] + weights[j].

The score after distributing the marbles is the sum of the costs of all the k bags.

Return the difference between the maximum and minimum scores among marble distributions.

Example 1:

Input: weights = [1,3,5,1], k = 2

Output: 4

Explanation:

The distribution [1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6.

The distribution [1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10.

Thus, we return their difference 10 - 6 = 4.

Example 2:

Input: weights = [1, 3], k = 2

Output: 0

Explanation: The only distribution possible is [1],[3].

Since both the maximal and minimal score are the same, we return 0.

Constraints:

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

题目大意

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

请你按照如下规则将所有的珠子放进 k 个背包。

  • 没有背包是空的。
  • 如果第 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

解题思路

  1. 边界权重和的计算：

    • 设定每一组的边界权重为该组的第一个和最后一个元素之和。
    • k = 1 时，不进行任何划分，返回 0。
    • k > 1 时，我们需要找到最大和最小的“边界权重和”之差。

  2. 计算所有相邻元素的和

    • 构造一个数组 pairSums，存储 weights[i] + weights[i+1] 的值，这些值代表可能的“边界权重和”。
    • 排序 pairSums，这样：
      • 最小的 k-1 个元素 可以用于构造最小的边界权重和 minSum。
      • 最大的 k-1 个元素 可以用于构造最大的边界权重和 maxSum。

  3. 计算结果

    • 计算 minSum：取 pairSums 最小的 k-1 项之和。
    • 计算 maxSum：取 pairSums 最大的 k-1 项之和。
    • 返回 maxSum - minSum 作为最终结果。

复杂度分析

  • 时间复杂度：O(n log n)，排序是主要的瓶颈。
    • 计算 pairSums：O(n)
    • 排序 pairSums：O(n log n)
    • 遍历计算 minSum 和 maxSum：O(k)
  • 空间复杂度：O(n)，存储 pairSums。

代码

/**
 * @param {number[]} weights
 * @param {number} k
 * @return {number}
 */
var putMarbles = function (weights, k) {
	if (k === 1) return 0;
	let pairSums = [];

	for (let i = 0; i < weights.length - 1; i++) {
		pairSums.push(weights[i] + weights[i + 1]);
	}

	pairSums.sort((a, b) => a - b);

	let minSum = 0,
		maxSum = 0;

	for (let i = 0; i < k - 1; i++) {
		minSum += pairSums[i];
		maxSum += pairSums[pairSums.length - 1 - i];
	}
	return maxSum - minSum;
};