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

以下是 LeetCode 2551「将珠子放入背包中」的 Java 实现。该题要求将 n 个珠子按顺序分成 k 个连续非空段每段得分 段内第一个珠子的重量 最后一个珠子的重量求所有分法中的最大总得分与最小总得分的差值。解题思路· 总得分可以表示为 weights[0] weights[n-1] 加上每个切割点段与段之间的边界的贡献 weights[i] weights[i1]其中 i 是切割位置。· 需要选择恰好 k-1 个切割点总得分 固定部分 所选切割点的 pairSum 之和。· 为了最大化总得分选择最大的 k-1 个 pairSum为了最小化选择最小的 k-1 个 pairSum。· 差值 (最大 k-1 个 pairSum 之和) - (最小 k-1 个 pairSum 之和)。· 特殊处理 k 1 或 k n 的情况此时只有一种分法差值为 0。javaimport 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-11最大最小4差值0 → 输出 0。