Medium

题目描述

给你一个正整数数组 nums。

将 nums 分割成两个数组 nums1 和 nums2，使得：

  • 数组 nums 中的每个元素都属于数组 nums1 或数组 nums2。
  • 两个数组都是 非空 的。
  • 分割的值 最小。

分割的值定义为 |max(nums1) - min(nums2)|。

这里，max(nums1) 表示数组 nums1 中的最大元素，min(nums2) 表示数组 nums2 中的最小元素。

返回表示这种分割的值的整数。

示例 1：

输入：nums = [1,3,2,4]
输出：1
解释：我们可以将数组 nums 分割为 nums1 = [1,2] 和 nums2 = [3,4]。
- 数组 nums1 的最大元素等于 2。
- 数组 nums2 的最小元素等于 3。
分割的值等于 |2 - 3| = 1。
可以证明 1 是所有分割中的最小值。

示例 2：

输入：nums = [100,1,10]
输出：9
解释：我们可以将数组 nums 分割为 nums1 = [10] 和 nums2 = [100,1]。
- 数组 nums1 的最大元素等于 10。
- 数组 nums2 的最小元素等于 1。
分割的值等于 |10 - 1| = 9。
可以证明 9 是所有分割中的最小值。

提示：

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这道题的关键洞察是：为了使分割值 |max(nums1) - min(nums2)| 最小，我们需要让 max(nums1) 和 min(nums2) 尽可能接近。

核心思路：

  1. 排序是关键：将数组排序后，相邻元素的差值是最小的。如果我们在某个位置将排序后的数组分割，左边部分的最大值和右边部分的最小值就是分割点两侧的相邻元素。

  2. 最优分割点：对于排序后的数组，如果在索引 i 和 i+1 之间分割，那么：

    • max(nums1) = nums[i]（左边部分的最大值）
    • min(nums2) = nums[i+1]（右边部分的最小值）
    • 分割值 = |nums[i] - nums[i+1]| = nums[i+1] - nums[i]

  3. 遍历所有可能的分割点：我们需要遍历所有可能的分割位置（索引0到n-2之间），找到使相邻元素差值最小的位置。

算法步骤：

  1. 将数组排序
  2. 遍历每个相邻元素对，计算差值
  3. 返回最小差值

这种方法的时间复杂度是O(n log n)，主要来自排序操作。

代码实现

class Solution {
public:
    int findValueOfPartition(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        int minDiff = INT_MAX;
        for (int i = 0; i < nums.size() - 1; i++) {
            minDiff = min(minDiff, nums[i + 1] - nums[i]);
        }
        
        return minDiff;
    }
};

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()
        
        min_diff = float('inf')
        for i in range(len(nums) - 1):
            min_diff = min(min_diff, nums[i + 1] - nums[i])
        
        return min_diff

public class Solution {
    public int FindValueOfPartition(int[] nums) {
        Array.Sort(nums);
        
        int minDiff = int.MaxValue;
        for (int i = 0; i < nums.Length - 1; i++) {
            minDiff = Math.Min(minDiff, nums[i + 1] - nums[i]);
        }
        
        return minDiff;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findValueOfPartition = function(nums) {
    nums.sort((a, b) => a - b);
    
    let minDiff = Infinity;
    for (let i = 0; i < nums.length - 1; i++) {
        minDiff = Math.min(minDiff, nums[i + 1] - nums[i]);
    }
    
    return minDiff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)排序操作需要 O(n log n)，遍历数组需要 O(n)
空间复杂度O(1)只使用常量额外空间（不考虑排序的额外空间）