DeepSeek LeetCode 2551. 将珠子放入背包中 Java实现

以下是 LeetCode 2551「将珠子放入背包中」的 Java 实现。该题要求将 n 个珠子按顺序分成 k 个连续非空段，每段得分 = 段内第一个珠子的重量 + 最后一个珠子的重量，求所有分法中的最大总得分与最小总得分的差值。

解题思路

· 总得分可以表示为 weights[0] + weights[n-1] 加上每个切割点（段与段之间的边界）的贡献 weights[i] + weights[i+1]，其中 i 是切割位置。
· 需要选择恰好 k-1 个切割点，总得分 = 固定部分 + 所选切割点的 pairSum 之和。
· 为了最大化总得分，选择最大的 k-1 个 pairSum；为了最小化，选择最小的 k-1 个 pairSum。
· 差值 = (最大 k-1 个 pairSum 之和) - (最小 k-1 个 pairSum 之和)。
· 特殊处理 k == 1 或 k == n 的情况，此时只有一种分法，差值为 0。

```java
import java.util.Arrays;

class Solution {
public long putMarbles(int[] weights, int k) {
int n = weights.length;
// 只有一种分法的情况
if (k == 1 || k == n) {
return 0L;
}

int m = n - 1;
long[] pairSums = new long[m];
for (int i = 0; i < m; i++) {
pairSums[i] = (long) weights[i] + weights[i + 1];
}
Arrays.sort(pairSums);

long minSum = 0L, maxSum = 0L;
for (int i = 0; i < k - 1; i++) {
minSum += pairSums[i];
maxSum += pairSums[m - 1 - i];
}
return maxSum - minSum;
}
}
```

复杂度分析

· 时间复杂度：O(n log n)，主要来自排序。
· 空间复杂度：O(n)，用于存储相邻元素和。

示例验证

· 输入：weights = [1,3,5,1], k = 2
相邻和：[4,8,6]，取最大 1 个 = 8，最小 1 个 = 4，差值 = 4 → 输出 4。
· 输入：weights = [1,3], k = 2
相邻和：[4]，k-1=1，最大=最小=4，差值=0 → 输出 0。