本文涉及知识点

C++贪心 临项交换

LeetCode910. 最小差值 II

给你一个整数数组 nums，和一个整数 k 。
对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。
nums 的 分数 是 nums 中最大元素和最小元素的差值。
在更改每个下标对应的值之后，返回 nums 的最小 分数 。
示例 1：
输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。
示例 2：
输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。
示例 3：
输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。
提示：
1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁴
0 <= k <= 10⁴

贪心之临项交换 + 排序

将nums按升序排序并去重。令x1 = nums[i] ,x2 = nums[i+1]。一定不存在x1-k,x2+k的情况，否则交换之。
交换前，这两个数的最大值：x2+k；交换后：max(x1+k,x2-k),显然最大值变小。
交换前，这两个数的最小值：x1-k;交换后：min(x1+k,x2-k)，显然最小值变大。
KaTeX parse error: Expected & or \\ or \cr or \end at end of input: …大值变小 && 其它情况\\ \end
最小值类似。
结论一：num[i]+k之前一定是没有元素或nums[i-1]+k。即+k在前，-k在后。
全部是+k或全部是-k，答案nums的最大值减nums的最小值。
枚举i，nums[0…i]全部+k,nums[i+1…]全部-k。则最大值是：max(nums[i]+k,nums.back()-k) 最小值是：min(nums[0]+k,nums[i+1]-k)
排序的时间复杂度：O(nlogn)，枚举的时间复杂度：O(n)
不去重也不影响结果。

代码

核心代码

	class Solution {
		public:
			int smallestRangeII(vector<int>& nums, int k) {
				const int N = nums.size();
				sort(nums.begin(), nums.end());	
				int ans = nums.back() - nums.front();
				for (int i = 0; i + 1 < N; i++) {
					ans = min(ans, max(nums[i] + k, nums.back() - k) - min(nums[0] + k, nums[i + 1] - k));
				}
				return ans;
			}
		};

单元测试

vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1 }, k = 0;
			auto res = Solution().smallestRangeII(nums, k);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 0,10 }, k = 2;
			auto res = Solution().smallestRangeII(nums, k);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 1,3,6 }, k = 3;
			auto res = Solution().smallestRangeII(nums, k);
			AssertEx(3, res);
		}