【LeetCode】每日一题 2024_10_21 最小差值 II(贪心)
前言
每天和你一起刷 LeetCode 每日一题~
LeetCode 启动!
题目:最小差值 II
代码与解题思路
func smallestRangeII(nums []int, k int) int {
// 今天这道题和昨天题目不同地方就在于,k 不是任意的了
// 那怎么样才能得到 nums 的最小分数?
// 让最大值-k,最小值+k,找到最小的情况
slices.Sort(nums)
ans, n := nums[len(nums)-1]-nums[0], len(nums)
for i := 1; i < n; i++ {
// 固定最大值-k,枚举最小值+k
mx := max(nums[i-1]+k, nums[n-1]-k)
// 固定最小值+k,枚举最大值-k
mi := min(nums[0]+k, nums[i]-k)
// 维护最小分数的情况
ans = min(ans, mx-mi)
}
return ans
}
核心思路:
为什么要固定最大值 nums[n-1]-k 枚举 nums[i-1]+k;固定 nums[0]+k 枚举 nums[i]-k ?为什么要用这样的遍历顺序?
在排序后,最后一个元素就是最大值,第一个元素就是最小值,题目要求找到最大元素和最小元素的差值(在对所有元素执行了 ± k 之后)
假设所有元素都是 +k 或者 -k,那得到的差值就是 nums[n-1] - nums[0],所以我将 ans 初始化为这个值
怎么样让差值尽可能的小?需要让大的值 -k,而小的值 +k,这样才有可能出现差值更小的情况
那我们枚举所有情况,即:第一个数变大,后面的数变小;前两个数变大,后面的数变小 . . . 最后一个数变小,前面的数变大
维护最小的差值即可。
每天进步一点点,我们明天不见不散~
可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。