当前位置：首页 > article >正文

LeetCode——最小差值

article 2024/10/28 12:34:28

文章目录

最小差值 part1
最小差值 part2

最小差值 part1

🍀思路：找到 nums 中最大值 max 和最小值 min，然后返回（max - k） + （min + k）即可。因为对于 nums 中的非最值 nums[ i ]：
在这里插入图片描述
🍀所以 nums 的最低分数为（max - k） + （min + k）。注意：如果（max - k） + （min + k）< 0，则返回 0

class Solution {
public:
	int smallestRangeI(vector<int>& nums, int k) {
		//找 nums 的最小值和最大值
		int min = 0, max = 0;
		for (int i = 1; i < nums.size(); i++) {
			if (nums[min] > nums[i]) {
				min = i;
			}
			if (nums[max] < nums[i]) {
				max = i;
			}
		}
		//返回 nums 的最小分数
		if (nums[max] - nums[min] < 2 * k) {
			return 0;
		}
		else return nums[max] - nums[min] - 2 * k;
	}
};

最小差值 part2

🍀分析：

对于 part1，我们可以通过调整 x 的值 [-k ~ k]，使得数组中所有的值调整到 [min + k ~ max - k] 的区间范围。并且如果 max - min - 2 * k < 0，则我们可以调整到 max - x == min - x，使得 nums 的最小分数为 0
对于 part2，因为 k 为定值，所以我们我们不能对 max 和 min 进行一定的调整，所以此时 max - min - 2 * k 不一定是 nums 的最小分数，甚至 max - k 与 min + k 都不一定是 nums 进行加减 k 处理后的最值，即 max - min - 2 * k 都不一定是 nums 的分数

max - min - 2 * k > 0

在这里插入图片描述

max - min - 2 * k < 0

在这里插入图片描述

🍀思路：小的变大，大的变小（参考了 leetcoed 的最优回答），举个栗子：

令 k = 3，有一个 nums 数组如下：

将所有数全都加 k：

所以正确思路如下：

🍀算法实现步骤如下：

//版本一
   int smallestRangeII(vector<int>& nums, int k) {
        std::sort(nums.begin(),nums.end());
        int min = INT32_MAX,max = INT32_MIN;
        int res = INT32_MAX;
        //对 nums 进行 n 次调整
        for(int i =0; i < nums.size(); i++){
            int count = 0;
            min = INT32_MAX, max = INT32_MIN;
            //找到每一次调整后的 nums 的分数
            for(auto e : nums){
                if(i >= count){
                    if(e + k > max){
                        max = e + k;
                    }
                    if(e + k < min){
                        min = e + k;
                    }
                    count++;
                }
                else{
                    if(e - k > max){
                        max = e - k;
                    }
                    if(e - k < min){
                        min = e - k;
                    }
                    count++;
                }
            }
            //判断是不是最小分数
            res > (max - min) ? res = max - min : res;
        }
        return res;
    }

//版本二
int smallestRangeII(vector<int>& nums, int k) {
	std::sort(nums.begin(), nums.end());
	if (nums.size() == 1)return 0;
	int max = nums.back(), min = nums[0];
	int res = max - min;
	for (int i = 1; i < nums.size(); i++) {
		//找到调整后 nums 的最小值和最大值
		min = nums[i] - k > nums[0] + k ? nums[0] + k : nums[i] - k;
		max = nums[i - 1] + k > nums.back() - k ? nums[i - 1] + k : nums.back() - k;
		//判断是否为 nums 最小分数
		res = (res > (max - min) ? (max - min) : res);
	}
	return res;
}