LeetCode|910. 最小差值 II(day19)

作者：MJ昊

博客：掘金、CSDN等

公众号：程序猿的编程之路

今天是 昊 的算法之路第19天，今天分享的是LeetCode第910题 最小差值 II的解题思路。这是一道中等难度的题目，考察如何通过调整数组中的数值来最小化最大值与最小值之间的差距。

题目描述简要回顾

给定一个整数数组nums和一个整数k，我们可以将数组中的每个元素加上或者减去一个不超过k的数。目标是找到经过调整后，数组的最大值与最小值的最小差。

解题思路

1. 为了使得最大差值最小，我们可以对数组先进行排序。然后考虑通过调整两个端点（即最大值和最小值）来求最小的差值。思路是：

2. 数组经过排序后，调整元素时，最大值要么是nums[n-1] - k，要么是nums[i] + k（调整左端）。
   最小值要么是nums[0] + k，要么是nums[i+1] - k（调整右端）。 通过逐步比较不同情况下的最大差值，找到最优解。

代码实现：

var smallestRangeII = function (nums, k) {
	nums.sort((a, b) => a - b);
	const n = nums.length;
	let res = nums[n - 1] - nums[0];
	for (let i = 0; i < n - 1; i++) {
		const maxVal = Math.max(nums[i] + k, nums[n - 1] - k);
		const minVal = Math.min(nums[0] + k, nums[i + 1] - k);
		res = Math.min(res, maxVal - minVal);
	}
	return res;
};

复杂度分析

• 时间复杂度： O(n log n)，主要是排序的时间复杂度。
• 空间复杂度： O(1)，只使用了常数空间。

总结

本题的核心在于排序后通过贪心的策略比较不同情况，找到最优的最小差值。通过调整最大值和最小值两端的元素，可以有效地控制差值的变化，最终得出最优解。