LeetCode 910. 最小差值 II

2025-10-13 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 910. 最小差值 II

题意分析

每个元素都必须被修改一次，且只有两种改法：加 k 或者减 k，不允许「不动」，也不允许加减别的数。改完之后要让整个数组的极差（最大值减最小值）尽可能小，返回这个最小极差。「必须改」这三个字是本题最容易被忽略的前提：不能靠把大数往下压、小数往上抬就直接抹平，因为每个数的位移幅度是固定的 k，只有方向可以选。

一共 n 个元素、每个两种选择，朴素地看是 $2^n$ 种方案。但约束里给的 n 只到一万量级，k 是非负整数，元素也全是非负整数，$2^n$ 显然不是出题意图；而「所有元素共用同一个 k」意味着任意两个元素之间的相对距离最多被扰动 2k，这个「有界扰动」的信号提示最终方案一定有很强的结构性，可以直接刻画出来而不是枚举出来。

边界上要注意几点：k 可以等于 0，此时任何方案都等价于原数组，答案就是原始极差；n 可以等于 1，此时唯一的元素无论加还是减，极差都是 0；元素允许重复，重复值完全可以被分到不同方向去；还有一个反直觉的情形——答案有可能就是原始极差本身，也就是「统一全加 k 或统一全减 k」反而最优，这个候选必须显式保留。

解法：排序 + 枚举分割点

核心思路

暴力做法是给每个元素独立枚举 +k 或 -k，共 $2^n$ 种组合，每种组合再扫一遍求极差，总代价 $O(n \cdot 2^n)$，n 稍大就完全不可行。

瓶颈在于我们把「每个元素的方向」当成了彼此独立的自由变量，实际上它们之间有极强的约束。先把数组排序，考察排序后任意两个位置 $i < j$：如果让较大的 nums[j] 加 k、较小的 nums[i] 减 k，这两个数被推得更远，差值从 nums[j] - nums[i] 扩大到 nums[j] - nums[i] + 2k；反过来让 nums[i] 加 k、nums[j] 减 k，它们被拉近。极差只会被「推远」的那一对拖累，所以把小的往上抬、把大的往下压永远不吃亏。

由此得到关键观察：在排序后的数组上，最优方案中「加 k 的集合」一定是一个前缀，「减 k 的集合」一定是一个后缀。假设不是——存在某个加 k 的位置排在某个减 k 的位置之后，把这两个的方向对调，按上一段的分析结果不会变差。于是只需枚举分割点，方案数从 $2^n$ 骤降到 n。

不变量因此可以写死：设分割点为 i（$0 \le i \le n-2$），下标 $[0, i]$ 全部加 k，下标 $[i+1, n-1]$ 全部减 k。这时结果数组的最大值只可能来自两个候选——加 k 组里最大的 nums[i] + k，或减 k 组里最大的 nums[n-1] - k，即 high = max(nums[i] + k, nums[n-1] - k)；最小值也只有两个候选——加 k 组里最小的 nums[0] + k，或减 k 组里最小的 nums[i+1] - k，即 low = min(nums[0] + k, nums[i+1] - k)。中间的元素永远夹在这四个候选之间，不可能成为极值，所以完全不必考虑。

最后还要把「不分割」这一种方案补上：所有元素同方向（全加或全减）时，整体平移不改变极差，答案就是 nums[n-1] - nums[0]。把它作为答案的初始值，再对每个分割点取 high - low 的最小值，就得到全局最优。

解题步骤

先排序。整个推导建立在「加 k 的是前缀、减 k 的是后缀」之上，而这个结论只在有序数组上成立；不排序的话「前缀」这个概念没有意义，分割点枚举也就无从谈起。

把答案初始化为 nums[n-1] - nums[0]。这一项代表「所有元素同方向」的方案，它不在任何分割点的枚举范围内（分割点要求两侧都非空），却真的可能是最优解，例如 k 很大时任何拆分都会把数组撑得更开。少了这个初始值，某些用例会返回一个比正确答案更大的数。

让 i 从 0 枚举到 n-2。i 表示加 k 组的最后一个下标，所以 i+1 必须是合法下标，上界只能取到 n-2；循环体里直接访问 nums[i+1]，边界就是这么定下来的，不需要额外的越界判断。

用 high = max(nums[i] + k, nums[n-1] - k) 求最大值。两个候选分别是两组各自的最大值：加 k 组的最大原值是 nums[i]，减 k 组的最大原值是 nums[n-1]。注意 nums[n-1] - k 不随 i 变化，但仍必须写进 max 里，因为它既可能大于也可能小于 nums[i] + k，两个方向都会出现。

用 low = min(nums[0] + k, nums[i+1] - k) 求最小值。对称地，加 k 组的最小原值是 nums[0]，减 k 组的最小原值是 nums[i+1]。

每轮用 high - low 更新答案取最小。每个分割点对应一个完整的合法方案，取所有方案的最小值即为全局最优，循环结束直接返回。

以 nums = [1, 3, 6], k = 3 走一遍：排序后仍是 [1, 3, 6]，n = 3，答案初始化为 6 - 1 = 5，对应全加 3 得到 [4, 6, 9] 或全减 3 得到 [-2, 0, 3]，两者极差都是 5。i = 0 时加 k 组是 [1]、减 k 组是 [3, 6]，high = max(1 + 3, 6 - 3) = max(4, 3) = 4，low = min(1 + 3, 3 - 3) = min(4, 0) = 0，差值 4，答案更新为 4；实际数组是 [4, 0, 3]，最大 4 最小 0，与公式吻合。i = 1 时加 k 组是 [1, 3]、减 k 组是 [6]，high = max(3 + 3, 6 - 3) = max(6, 3) = 6，low = min(1 + 3, 6 - 3) = min(4, 3) = 3，差值 3，答案更新为 3；实际数组是 [4, 6, 3]，最大 6 最小 3，同样吻合。循环结束，返回 3。

代码实现

// 枚举分割点 i，最大值为 max(nums[i] + K, nums[n-1] - K)。
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;
    }
}

// 枚举分割点 i，最大值为 max(nums[i] + K, nums[n-1] - K)。
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)$，其中 n 为数组长度。凭什么？排序占 $O(n \log n)$，之后只有一趟从 0 到 n-2 的循环，每轮做的都是常数次比较与减法，没有嵌套循环也没有重复扫描，线性部分被排序完全吞掉，总复杂度由排序主导。

空间复杂度：$O(\log n)$。凭什么？算法本身只用了 answer、high、low、i 这几个标量，是严格 $O(1)$ 的；额外开销全部来自排序的递归栈——Java 的双轴快排与 Go 的 sort.Ints 都原地交换但递归深度为 $O(\log n)$。若把排序视作输入预处理，则算法自身的额外空间为 $O(1)$。

关键点总结

「必须操作」和「可以操作」是两道完全不同的题：可选操作时贪心地把极值往中间收即可，强制操作时每个元素都被迫位移，必须同时考虑位移带来的反向撑开。读题时把这个词圈出来，能省掉一半的错误方向。

交换论证是把指数降到线性的标准工具：证明「最优解中加 k 的一定是前缀」用的就是「假设存在一对逆序，交换它们的方向后不会变差」这个套路。任何「每个元素二选一」的贪心题都可以先试这一招，成功了方案空间立刻塌缩成枚举一个分界。

极值只可能出现在候选集合的端点：排序后分成两组，最大值必在两组各自的最大值之间产生，最小值必在两组各自的最小值之间产生，中间元素可以直接忽略。识别出这一点，才能把每轮判断压到 $O(1)$ 而不是重新扫一遍数组。

不要漏掉退化方案：分割点枚举天然排除了「一侧为空」的情况，而这恰恰是 k 很大时的最优解。写完循环回头问一句「有没有哪种合法方案不在我的枚举范围里」，是这类题的必备自检。

面试视角：面试官关心的不是你能不能背出那两行 max/min，而是能不能说清「为什么加 k 的一定是前缀」。开口先给交换论证，再写公式，最后主动补一句「答案初始值就是全同向的方案」，基本就是满分答法。如果被追问变体「每个数可以加 $[-k, k]$ 中的任意值」，那就退化成把区间往中间收，答案是 $\max(0, nums[n-1] - nums[0] - 2k)$，两种版本对照着讲会显得体系很清晰。

易错点总结

错误写法：忘记排序直接枚举分割点。用例 nums = [3, 1, 6], k = 3 → i = 0 时算出 high = max(3+3, 6-3) = 6、low = min(3+3, 1-3) = -2，差值 8，比正确答案 3 大得多；「前缀加 k」的结论只在有序数组上成立，乱序时枚举的根本不是合法的最优结构。

错误写法：答案初始化为 Integer.MAX_VALUE 而不是 nums[n-1] - nums[0]。用例 nums = [1, 3, 6], k = 100 → 两个分割点给出的差值分别是 101 - (-97) = 198 与 103 - (-94) = 197，而全同向方案只有 5；漏掉初始值会返回 197。

错误写法：循环写成 i < n。用例 nums = [1, 3, 6], k = 3 → i 取到 2 时访问 nums[3]，Java 抛 ArrayIndexOutOfBoundsException、Go 直接 panic；分割点必须保证减 k 组非空，上界只能是 n-2。

错误写法：low 里写成 nums[i] - k 而不是 nums[i+1] - k。用例 nums = [1, 3, 6], k = 3 → i = 1 时 low = min(4, 3 - 3) = 0，差值算成 6，而正确的 low = min(4, 6 - 3) = 3、差值 3；nums[i] 属于加 k 组，把它当作减 k 组的最小值等于让同一个元素同时用了两种方向。

错误写法：high 只写 nums[i] + k，漏掉 nums[n-1] - k。用例 nums = [0, 10], k = 2 → i = 0 时 high 被算成 2，low = min(2, 8) = 2，差值 0，但真实数组是 [2, 8]、极差 6；当 2k 小于组间落差时，减 k 组的最大值才是全局最大值。

错误写法：凭直觉固定在中点分割而不枚举。用例 nums = [1, 90, 100], k = 10 → 固定 i = 1 得到 high = max(100, 90) = 100、low = min(11, 90) = 11，差值 89；而 i = 0 时 high = max(11, 90) = 90、low = min(11, 80) = 11，差值 79 才是答案。最优分界与元素分布有关，必须全部枚举。

错误写法：把结果数组真的构造出来再求极差。用例 n = 10^4 → 每个分割点重建一次数组并扫描求最值，总代价 $O(n^2)$ 约一亿次操作，在时限边缘反复横跳；四个候选值已经完全刻画了极值，没有任何理由物化整个数组。

错误写法：为 k = 0 单独加特判并直接 return 0。用例 nums = [1, 3, 6], k = 0 → 正确答案是 5（数组根本没变），返回 0 属于凭空捏造；主逻辑本身就能给出 high = 6、low = 1、差值 5，多余的特判只会引入 bug。

错误写法：Go 里用 sort.Slice 配一个写反的比较函数。写成 sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] }) 后数组变成降序，用例 nums = [1, 3, 6], k = 3 → 初始答案变成 nums[n-1] - nums[0] = 1 - 6 = -5，一个负的极差被当成最优值直接返回。整型数组直接用 sort.Ints 最省心。

相似题目

题目	难度	考察点
1029. 两地调度	中等	同样是排序后按前缀/后缀分两组，但排序键是两种代价之差而非原值本身
561. 数组拆分	简单	排序后相邻两两配对，用交换论证证明最优，不需要枚举任何分界
881. 救生艇	中等	排序后用首尾双指针做配对决策，分组由指针动态推进而不是一个静态分割点
452. 用最少数量的箭引爆气球	中等	按右端点排序后扫描并维护当前射程，贪心对象是区间覆盖而非数值位移
1005. K 次取反后最大化的数组和	简单	同为「元素被迫做符号选择」，但操作次数受限且要处理取反的奇偶剩余
1675. 数组的最小偏移量	困难	目标同样是最小化极差，但操作可反复执行，需要用堆动态维护当前最大值