最小化两组极差之和

题目描述

给定 n 个整数，需要将它们任意分成两组，且两组都不能为空。

对于一组数，它的极差定义为该组中的最大值减去最小值。目标：最小化这两个极差之和，即 (max1 - min1) + (max2 - min2)。输出这个最小值。

数据范围：

• 1 ≤ n ≤ 10⁵
• 数组元素为整数

示例

示例1：

输入：5,[10,1,5,3,8]
输出：6

说明：划分为 [10,8] 和 [1,5,3] 两组：左极差 = 5-1 = 4，右极差 = 10-8 = 2，总和 = 6。

示例2：

输入：5,[1,1,9,1,9]
输出：0

说明：分组为 [1,1,1] 和 [9,9]，两组的极差均为 0，和为 0。

示例3：

输入：2,[1,2]
输出：0

说明：分组为 [1] 和 [2]，两组极差均为 0，和为 0。

解题思路

关键洞察： 排序后，最优分组必然是将数组在某个位置“切开”。

排序后，数组变为 [a₀, a₁, ..., a_{n-1}]。

假设第 1 组包含 a₀（最小值），第 2 组包含 a_{n-1}（最大值），那么：

• 第 1 组的极差至少为 0
• 第 2 组的极差至少为 0

最优分组策略： 排序后，在第 i 个位置（1 ≤ i < n）切开：

• 第 1 组：[a₀, ..., a_{i-1}]，极差 = a_{i-1} - a₀
• 第 2 组：[a_i, ..., a_{n-1}]，极差 = a_{n-1} - a_i
• 总极差 = (a_{i-1} - a₀) + (a_{n-1} - a_i)

遍历所有可能的切分点 i，取最小值。

特例： n ≤ 2 时，直接返回 0（两组各一个元素，极差均为 0）。

代码实现

function getResult(n, nums) {
    if (n <= 2) return 0;
    nums.sort((a, b) => a - b);
    let min = Infinity;
    for (let i = 1; i < n; i++) {
        const leftRes = nums[i - 1] - nums[0];
        const rightRes = nums[n - 1] - nums[i];
        min = Math.min(min, leftRes + rightRes);
    }
    return min;
}

复杂度分析

• 时间复杂度： O(n log n)，排序占主导。遍历切分点为 O(n)。
• 空间复杂度： O(1)，原地排序，常数额外空间。

5,[10,1,5,3,8]

6