算法题最小差值 I-程序员充电站

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。

算法思路

贪心策略：

找到原数组的最大值maxNum和最小值minNum
目标是让最大值尽可能小，最小值尽可能大
最优策略是：
- 将最小值增加k（变为minNum + k）
- 将最大值减少k（变为maxNum - k）
如果minNum + k >= maxNum - k，说明可以将所有元素调整到同一个值，差值为0
否则，最小差值为(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

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

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

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

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

找到minNum = 1,maxNum = 1
计算adjustedMin = 1 + 0 = 1
计算adjustedMax = 1 - 0 = 1
由于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}