2740-找出分区值

给你一个 正 整数数组 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 <= 105
• 1 <= nums[i] <= 109

下午两点【biIibiIi@灵茶山艾府】 直播讲题，不仅讲做法，还会教你如何一步步思考，记得关注哦~

---

答案的理论最小值，是任意两个元素的差的绝对值的最小值。能否取到这个最小值呢？

是可以的，把数组排序后，最小值必然对应两个相邻元素，设其为 nums}[i-1] 和 nums}[i]。

把不超过 nums}[i-1] 的数分到第一个数组中，把不低于 nums}[i] 的数分到第二个数组中，即可满足题目要求。

[sol-Python3]

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()
        return min(y - x for x, y in pairwise(nums))

[sol-Go]

func findValueOfPartition(nums []int) int {
	sort.Ints(nums)
	ans := math.MaxInt
	for i := 1; i < len(nums); i++ {
		ans = min(ans, nums[i]-nums[i-1])
	}
	return ans
}

func min(a, b int) int { if b < a { return b }; return a }

复杂度分析

• 时间复杂度：\mathcal{O}(n\log n)，其中 n 为 nums 的长度。瓶颈在排序上。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。