【线性枚举】力扣910-最小差值2

摘要: Ad-Hoc 问题，算法就是个线性枚举，但难在分析清楚问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，今天我们来看一个稍微有点统计学背景的题，涉及到描述性统计中的极差的概念。给定一组既定的数据，对每条数据都必须选择 $+k$ 或者 $-k$，最终目标是使得极差最小。

分析清楚问题之后，会定下一个先排序，然后枚举每个元素更新最优解的算法。算法核心就是个线性枚举，但分析问题的过程比较复杂。

注意排序之后的枚举过程不是贪心算法，它不是说在 $i$ 位置仅考虑如何操作 $A[i]$ 会使得 $A[0..i]$ 这个局部的极差最小就选择哪个操作；而是枚举到 $i$ 时，直接对应到一个完整问题的可行解，用该可行解直接更新答案，所以这就是个简单的枚举，而不是贪心。

题目

• 910. 最小差值 II

给你一个整数数组 nums，和一个整数 k 。

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的 分数 是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小 分数 。

提示：

1 <= nums.length <= 1e4
0 <= nums[i] <= 1e4
0 <= k <= 1e4

示例 1：
输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。

示例 2：
输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。

示例 3：
输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。

题解

算法: 分析问题，排序+枚举

假设原始数据中最大值为 $h$，最小值为 $l$，极差 $d = h - l$，那么操作之后，极差至少不应该比 $d$ 还大，因为可以选择每个数据都做一样的操作，就可以使极差不变。

由于 $k \geq 0$，因此要让极差变小，直观上需要将一些小的数 $+k$，将一些大的数 $-k$。假设经过最优解的操作后，最大值变为 $h’$，最小值变为 $l’$，那么新的极差变为 $d’ = h’ - l’$。我们的操作要使得 $h’$ 尽可能小，$l’$ 尽可能大。

假设最优解在元素值 $x$ 上的操作为 $+k$，那么 $x’ = x + k \geq h’$，此时对于一个比 $x$ 更小的元素 $y$，在 $y$ 上的操作也选择 $+k$ 的结果至少不会比选择 $-k$ 更差。

因为 $y < x$，那么就有 $y + k < x + k \leq h’$，$y - k$ 自然肯定也小于 $h’$，因此 $y$ 上的操作不论是 $+k$ 还是 $-k$ 肯定不会影响到 $h’$。因此对 $y$ 的操作想要对结果有影响，就只能是影响 $l’$。若此时 $y$ 的操作是 $-k$，就肯定有 $l’ \leq y-k$，那么将操作改为 $+k$，得到的新值当然就有 $y + k \geq y - k \geq l’$。于是我们可以有以下结论：

若最优解在 $x$ 上的操作是 $+k$，那么对于任意小于 $x$ 的元素 $y$，将 $y$ 上的操作从 $-k$ 改为 $+k$，肯定不会对 $h’$ 产生影响，同时至少不会使得 $l’$ 更小。那么直接将所有小于 $x$ 的元素都选择 $+k$ 即可。

类似地，若最优解在 $x$ 上的操作是 $-k$，那么对所有大于 $x$ 的元素都选择 $-k$ 操作即可。总结下来就是，最优解会以某个值 $s$ 作为分界线，$\leq s$ 的元素都是 $+k$ 操作，$> s$ 的元素都是 $-k$ 操作，问题就在于 $n$ 个值中那一个是我们要找的 $s$。

假设最原数据中最大元素 $h$ 选择 $-k$ 操作（若 $h$ 做 $+k$ 操作，根据前面的结论，所有元素都得 $+k$，极差不变），最小元素 $l$ 的情况类似，选择 $+k$ 操作。在此基础上考虑 $s$ 的情况：

一方面有 $h’ = \max(s + k, h - k)$；另一方面，假设原数据中比 $s$ 大的最小元素是 $t$，由于 $t > s$，因此 $t$ 的操作是 $-k$，这有可能使得 $t - k$ 成为了新数组的最小值，即 $l’ = \min(t - k, l + k)$。

这样我们就有了最终算法：枚举 $s$，用将 $s$ 作为操作的分界点所得的新极差 $\max(s + k, h - k) - \min(t - k, l + k)$ 更新答案。

这里对于每个枚举到的 $s$，都需要查询数组中 $s$ 的后继，要实现这个查询最直接的办法就是排序后，按顺序枚举 $i=0,1,\cdots,n-2$，这样 $A[i+1]$ 就是 $A[i]$ 的后继。

所以完整的算法避不开一个排序，时间复杂度为 $O(N\log N)$。

代码 (C++)

class Solution {
public:
    int smallestRangeII(vector<int>& A, int k) {
        sort(A.begin(), A.end());
        int n = A.size();
        int h = A[n - 1];
        int l = A[0]; 
        int d = h - l;
        for(int i = 0; i < n - 1; ++i)
        {
            // [0..i] + K, [i+1..n-1] -K
            int s = A[i];
            int t = A[i + 1];
            d = min(d, max(s + k, h - k) - min(t - k, l + k));
        }
        return d;
    }
};

代码 (Python)

class Solution:
    def smallestRangeII(self, A: List[int], k: int) -> int:
        A.sort()
        n = len(A)
        l, h = A[0], A[n - 1]
        d = h - l
        for i in range(n - 1):
            s, t = A[i], A[i + 1]
            d = min(d, max(s + k, h - k) - min(t - k, l + k))
        return d

---