Problem
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 andjth
marble are in a bag, then all marbles with an index between theith
andjth
indices should also be in that same bag.If a bag consists of all the marbles with an index from
i
toj
inclusively, then the cost of the bag isweights[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
Solution
/**
* @param {number[]} weights
* @param {number} k
* @return {number}
*/
var putMarbles = function(weights, k) {
var arr = [];
for (var i = 0; i < weights.length - 1; i++) {
arr.push(weights[i] + weights[i + 1]);
}
arr.sort((a, b) => a - b);
var min = arr.slice(0, k - 1).reduce((sum, num) => sum + num, 0);
var max = arr.slice(arr.length - k + 1).reduce((sum, num) => sum + num, 0);
return max - min;
};
Explain:
nope.
Complexity:
- Time complexity : O(nlog(n)).
- Space complexity : O(n).