LeetCode 910. 最小差值 II
题目描述
题意分析
每个元素都必须选择加
k或减k，目标是让修改后的最大值与最小值之差尽可能小。每项只能取这两个结果，不能在中间任意调整；调整后出现负数是允许的。代码先排序，会改变输入顺序。
解法：排序 + 枚举分割点
核心思路
[!blue]
排序后，只需考虑“前缀全部加
k，后缀全部减k”的方案。理由是：若较小的数x减k，较大的数y加k，原来的两个结果为x - k、y + k；交换选择后得到x + k、y - k，二者仍落在原区间[x - k, y + k]内，所以整体极差不会扩大。反复消除这种“前面减、后面加”的选择，就能把任意方案整理成前加后减，且答案不会变差。因此至少存在一个这种形式的最优解，枚举分界就足够，无需枚举每个元素的两种选择。
分界放在
i与i + 1之间时，前缀最小、最大值分别为nums[0] + k、nums[i] + k，后缀分别为nums[i + 1] - k、nums[n - 1] - k。两段内部顺序不变，取两段最大值中的较大者作为high，最小值中的较小者作为low，当前极差便是high - low。全部加或全部减也属于合法方案，二者极差都等于原极差，用它初始化答案。这样只需枚举两段都非空的内部切分，不会漏掉边界方案。
解题步骤
- 将数组升序排序，用
nums[n - 1] - nums[0]初始化答案。- 枚举
i = 0..n-2，令左侧加k、右侧减k。- 计算
high = max(nums[i] + k, nums[n - 1] - k)和low = min(nums[0] + k, nums[i + 1] - k)，用high - low更新答案。- 返回所有方案中的最小极差。单元素没有内部分界，直接返回 0；
k = 0时所有方案都保留原极差。
代码实现
class Solution {
public int smallestRangeII(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
// 全部同向修改的极差等于原极差。
int answer = nums[n - 1] - nums[0];
for (int i = 0; i < n - 1; i++) {
// 分界左侧加、右侧减，分别比较两个分段的极值。
int high = Math.max(nums[i] + k, nums[n - 1] - k);
int low = Math.min(nums[0] + k, nums[i + 1] - k);
answer = Math.min(answer, high - low);
}
return answer;
}
}
import "sort"
func smallestRangeII(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
// 全部同向修改的极差等于原极差。
answer := nums[n-1] - nums[0]
for i := 0; i < n-1; i++ {
// 分界左侧加、右侧减，分别比较两个分段的极值。
high := nums[n-1] - k
if nums[i]+k > high {
high = nums[i] + k
}
low := nums[0] + k
if nums[i+1]-k < low {
low = nums[i+1] - k
}
if high-low < answer {
answer = high - low
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n\log n)$。排序占主导，枚举分界只需 $O(n)$。
- 空间复杂度：扫描使用 $O(1)$ 额外空间，另计标准库排序的辅助空间。
关键点总结
[!green]
- 交换论证证明存在一个分界型最优解，不要求每个最优方案都采用相同形式。
- 分界后两段各自有序，但两段之间可能交错，所以新极值必须从两段端点共同选取。
- 原极差是全部同向调整的合法结果，不代表允许所有元素保持不动。
易错点总结
[!yellow]
- 只修改原最大值和最小值，会忽略中间元素调整后成为新的极值。
- 只比较分界两边的相邻值，会漏掉两段另外一端的候选极值。
- 不能把负的调整结果舍弃；本题没有要求修改后的元素非负。
- 不保留原极差，会漏掉全部加、全部减以及单元素的情况。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 908. 最小差值 I | 简单 | 原题每项可在±k范围内任意调整，本题只能选择加k或减k，需要保留离散选择约束。 |
| 632. 最小区间 | 困难 | 每项有x-k与x+k两个候选，可视为从每组取一点的最小覆盖区间；本题统一偏移量允许更简单的排序分割。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！