每日一题(2022-04-30)—— 最小差值 I

908. 最小差值 I

题目描述：

给你一个整数数组 nums，和一个整数 k 。 在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的整数。对于每个索引 i ，最多 只能 应用 一次 此操作。 nums 的 分数 是 nums 中最大和最小元素的差值。 在对 nums 中的每个索引最多应用一次上述操作后，返回nums的最低 分数 。

大致题意： 通过对现有数组的元素+x（每个元素只有一个次+x的机会），使得新数组的最大值和最小值之间的差值最小。

示例1： 输入：nums = [1], k = 0 输出：0 解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。 示例2： 输入：nums = [0,10], k = 2 输出：6 解释：将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6

思路：

• 当原数组的最大值 - 最小值 > 2 * k，那么把最小值 + k，最大值 - k，得到的新数组的最大值和最小值的差最小。
• 否则，得到的新数组的最大值和最小值的差就是 0（因为x取值是[-k,k],如果你最大和最小相差小于2k，那么你都可以通过在[-k,k]这个范围里，找到值，使数组里的所有元素都变成一样）

题解：

func smallestRangeI(nums []int, k int) int {
	maxNum,minNum := sortNums(nums)
	return max(0, maxNum-k-(minNum+k))
}

func sortNums(nums []int) (max, min int) {
	max = nums[0]
	min = nums[0]
	for i := 0; i < len(nums); i++ {
		if nums[i] > max {
			max = nums[i]
		}
		if nums[i] < min {
			min = nums[i]
		}
	}
	return max, min
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

提交结果：

在这里插入图片描述