将珠子放入背包中

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 <= 105
• 1 <= weights[i] <= 109

// Java Stream solution
// 思路：使用Java Stream API来计算所有可能的背包价格，然后找到最大和最小价格的差值。

import java.util.Arrays;
import java.util.stream.IntStream;

public class BeadsDistributionStream {
    public int maxMinDifference(int[] weights, int k) {
        int n = weights.length;
        // 计算每个可能的背包价格
        int[] prices = IntStream.range(0, n - 1)
                .map(i -> weights[i] + weights[i + 1])
                .sorted()
                .toArray();
        int minPrice = IntStream.range(0, k - 1).map(i -> prices[i]).sum();
        int maxPrice = IntStream.range(0, k - 1).map(i -> prices[n - 2 - i]).sum();
        return maxPrice - minPrice;
    }

    public static void main(String[] args) {
        BeadsDistributionStream bds = new BeadsDistributionStream();
        int[] weights = {1, 3, 5, 1};
        int k = 2;
        System.out.println(bds.maxMinDifference(weights, k)); // 输出：4
    }
}

题解的主要思路是首先计算所有相邻珠子的和，存储在一个数组中。然后将这个数组排序，以便于选出珠子组合的最大和最小值。具体步骤如下：1. 首先对于每一对相邻的珠子，计算它们的重量和，形成一个新的数组。2. 将这个新数组进行排序。3. 从排序后的数组中，为了获得最大分数，选择末尾的k-1个元素（因为这些是最大的k-1个组合），并计算它们的和。4. 同时，为了保证没有空背包，计算前k-1个元素（最小的k-1个组合）的和。5. 最终得分是最大组合和减去最小组合和。

O(n log n)

O(n)