本文涉及知识点

C++贪心

LeetCode2567. 修改两个元素的最小分数

1509几乎和本题相同
给你一个下标从 0 开始的整数数组 nums 。
nums 的 最小 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
nums的 最大 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
nums 的分数是 最大 得分与 最小 得分的和。
我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。
请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。
|x| 表示 x 的绝对值。
示例 1：
输入：nums = [1,4,3]
输出：0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。
示例 2：
输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。
提示：
3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

贪心

将任意nums[i]修改成nums[j]，最小值就是0。
将nums排序，要想减少最大值，必须：
一，修改nums[n-1]。然后修改nums[n-1]或nums[0]。
二，修改nums[0]，然后修改nums[1]或nums[n-1]。
共三种情况：
将nums[0]和nums[1]修改成nums[2]。最大值为：nums.back()-nums[2]。
将nums[n-1]和nums[n-2]修改成nums[n-3]。最大值nums[n-3]- nums[0]。
将nums[0]和nums[n-1]修改成nums[1]。最大值为nums[n-2]-num[1]。
三种情况最小值都为0。

代码

核心代码

class Solution {
		public:
			int minimizeSum(vector<int>& nums) {
				const int N = nums.size();
				sort(nums.begin(), nums.end());
				int ans = min(nums.back() - nums[2], nums[N - 3] - nums[0]);
				return min(ans, nums[N - 2] - nums[1]);
			}
		};

单元测试

vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, 4, 3 };
			auto res = Solution().minimizeSum(nums);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,4,7,8,5 };
			auto res = Solution().minimizeSum(nums);
			AssertEx(3, res);
		}