惠州市网站建设_网站建设公司_数据统计_seo优化

908. 最小差值 I

问题描述

给你一个整数数组nums和一个整数k。你可以选择数组中的任一元素并将其替换为[num - k, num + k]范围内的任意整数。

在应用此操作至多一次后，求数组中最大值和最小值之间的最小可能差值。

示例：

输入: nums = [1], k = 0 输出: 0 解释: 数组只有一个元素，最大值和最小值相同，差值为0。 输入: nums = [0,10], k = 2 输出: 6 解释: 将0变为2，将10变为8，数组变为[2,8]，差值为6。 输入: nums = [1,3,6], k = 3 输出: 0 解释: 将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。

算法思路

贪心策略：

1. 找到原数组的最大值maxNum和最小值minNum
2. 目标是让最大值尽可能小，最小值尽可能大
3. 最优策略是：
   • 将最小值增加k（变为minNum + k）
   • 将最大值减少k（变为maxNum - k）
4. 如果minNum + k >= maxNum - k，说明可以将所有元素调整到同一个值，差值为0
5. 否则，最小差值为(maxNum - k) - (minNum + k) = maxNum - minNum - 2*k

代码实现

方法一：直接计算

classSolution{/** * 计算应用操作后数组最大值和最小值的最小可能差值 * * @param nums 输入整数数组 * @param k 可调整的范围参数 * @return 最小可能差值 */publicintsmallestRangeI(int[]nums,intk){// 找到数组中的最大值和最小值intminNum=nums[0];intmaxNum=nums[0];for(intnum:nums){minNum=Math.min(minNum,num);maxNum=Math.max(maxNum,num);}// 计算调整后的最小差值// 最小值最多可以增加到 minNum + k// 最大值最多可以减少到 maxNum - kintadjustedMin=minNum+k;intadjustedMax=maxNum-k;// 如果调整后的最小值 >= 调整后的最大值，说明可以完全重合，差值为0if(adjustedMin>=adjustedMax){return0;}// 否则返回调整后的差值returnadjustedMax-adjustedMin;}}

方法二：优化

classSolution{/** * 优化 * * @param nums 输入整数数组 * @param k 可调整的范围参数 * @return 最小可能差值 */publicintsmallestRangeI(int[]nums,intk){intminNum=Arrays.stream(nums).min().getAsInt();intmaxNum=Arrays.stream(nums).max().getAsInt();returnMath.max(0,maxNum-minNum-2*k);}}

算法分析

• 时间复杂度：O(n)
  • 需要遍历数组一次找到最大值和最小值
• 空间复杂度：O(1)
  • 只使用了常数个额外变量

算法过程

输入：nums = [1,3,6], k = 3

1. 找到minNum = 1,maxNum = 6
2. 计算adjustedMin = 1 + 3 = 4
3. 计算adjustedMax = 6 - 3 = 3
4. 由于4 >= 3，返回0

输入：nums = [0,10], k = 2

1. 找到minNum = 0,maxNum = 10
2. 计算adjustedMin = 0 + 2 = 2
3. 计算adjustedMax = 10 - 2 = 8
4. 由于2 < 8，返回8 - 2 = 6

输入：nums = [1], k = 0

1. 找到minNum = 1,maxNum = 1
2. 计算adjustedMin = 1 + 0 = 1
3. 计算adjustedMax = 1 - 0 = 1
4. 由于1 >= 1，返回0

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：单元素数组int[]nums1={1};System.out.println("Test 1: "+solution.smallestRangeI(nums1,0));// 0// 测试用例2：标准示例int[]nums2={0,10};System.out.println("Test 2: "+solution.smallestRangeI(nums2,2));// 6// 测试用例3：可以完全重合int[]nums3={1,3,6};System.out.println("Test 3: "+solution.smallestRangeI(nums3,3));// 0// 测试用例4：k为0（无法调整）int[]nums4={2,7,2};System.out.println("Test 4: "+solution.smallestRangeI(nums4,0));// 5// 测试用例5：大k值int[]nums5={1,3,6};System.out.println("Test 5: "+solution.smallestRangeI(nums5,10));// 0// 测试用例6：负数int[]nums6={-1,-3,-6};System.out.println("Test 6: "+solution.smallestRangeI(nums6,2));// 0// 测试用例7：大数组int[]nums7={100,200,300,400,500};System.out.println("Test 7: "+solution.smallestRangeI(nums7,50));// 300// 测试用例8：k刚好让差值为0int[]nums8={1,5};System.out.println("Test 8: "+solution.smallestRangeI(nums8,2));// 0}

关键点

1. 贪心策略：

   • 由于每个元素可以独立调整，最优策略就是让最小值最大化，最大值最小化
   • 中间元素的调整不会影响最终的最值差

2. 边界处理：

   • 当minNum + k >= maxNum - k时，差值为0
   • 差值不能为负数，所以要和0取最大值

3. 数学公式：

   • max(0, maxNum - minNum - 2*k)

4. 特殊情况：

   • 单元素数组：差值恒为0
   • k=0：无法调整，返回原始差值
   • 大k值：可能让所有元素重合

常见问题

1. 为什么不需要考虑中间元素的调整？

   • 只关心最终数组的最大值和最小值
   • 中间元素即使调整，也不会成为新的最大值或最小值（在最优策略下）

2. 为什么是2*k而不是k？

   • 同时调整了最小值（+k）和最大值（-k）
   • 总共可以减少k + k = 2*k的差值