【LeetCode周赛246】D LeetCode 1906. 查询差绝对值的最小值

摘要：
前缀和配合计数排序，妙哉~！

题目

一个数组 a 的 差绝对值的最小值 定义为：0 <= i < j < a.length 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值。如果 a 中所有元素都相同，那么差绝对值的最小值为 -1 。

比方说，数组 [5,2,3,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0 ，因为 a[i] 和 a[j] 必须不相等。

给你一个整数数组 nums 和查询数组 queries ，其中 queries[i] = [li, ri] 。对于每个查询 i ，计算 子数组 nums[li...ri] 中 差绝对值的最小值 ，子数组 nums[li...ri] 包含 nums 数组（下标从 0 开始）中下标在 li 和 ri 之间的所有元素（包含 li 和 ri 在内）。

请你返回 ans 数组，其中 ans[i] 是第 i 个查询的答案。

子数组 是一个数组中连续的一段元素。

|x| 的值定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。

示例 1：

输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
输出：[2,1,4,1]
解释：查询结果如下：
– queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
– queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
– queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
– queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。

示例 2：

输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
输出：[-1,1,1,3]
解释：查询结果如下：
– queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。
– queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。
– queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。
– queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。

提示：

$2 <= nums.length <= 10^5$
$1 <= nums[i] <= 100$
$1 <= queries.length <= 2 * 10^4$
$0 <= li < ri < nums.length$

前缀和

先想想朴素做法，我们可以对于每一段查询获取一个子数组，对子数组排序，找到相邻数字差绝对值最小的数。

注意到数组元素的取值范围是 $1 <= nums[i] <= 100$, 因为范围很小所以很容易联想到计数排序。既然需要对子数组元素计数，自然联想到前缀和。

可以开一个二维数组，行表示为数组下标$+1$(因为前缀和需要考虑0的情况，避免出现值-1的下标)；列表示数组元素值在 $[1,100]$ 中的某个数。

遍历数组中的每个元素，再以当前元素为结束的前缀数组中，遍历 $[1,100]$ 中的每个数，对前缀数组进行计数。
注意当前行需要继承前一行的非零值。

举例：
对于数组 nums = [1,3,4,8] ,预处理出的前缀和数组为：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

那么可以在 $O(1)$ 的时间复杂度下得到某一段子数组如第2到3的所有元素计数情况。接着，可以在 $O(N)$ 的复杂度下得到这段子数组的最小差绝对值。

class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        int len = nums.size();

        vector<vector<int>> presum(len + 10, vector<int>(110, 0));
        
        // presum 
        for (int i = 1; i <= len; i++) {                    // 第i行放入数组前0 ~ i - 1项的和，即从1开始数组第某项放在第某行中
            for (int j = 1; j <= 100; j++) {
                if (presum[i - 1][j]) {
                    presum[i][j] = presum[i - 1][j];
                }
            }
            presum[i][nums[i - 1]]++;
        }

        /*
        for (int i = 0; i <= len; i++) {
            for (int j = 0; j <= 100; j++) {
                cout << presum[i][j] << ' ';
            }
            cout << endl;
        }
        */
        vector<int> res;
        for (int i = 0; i < queries.size(); i++) {          // 对于每组查询，依次找到子数组中的数，找到最小差绝对值
            int l = queries[i][0] + 1, r = queries[i][1] + 1;   // 加1是因为l r是数组下标从0记起，而我们的前缀和是从1记起
            int tres = 110, last = 0;
            for (int j = 1; j <= 100; j++) {                // 从小到大遍历子数组中的数
                if (presum[r][j] - presum[l - 1][j] > 0) {  // 找到一个子数组中的数
                    if (last) {                             // 如果当前子数组的数不是第一个（可以产生一个差绝对值）
                        tres = min(tres, j - last);         // 当前子数组的数和上一个子数组的数绝对值差为 j - last
                    }
                    last = j;                               // 不管当前数字是不是第一个子数组的数，last 都要更新为当前子数组的数
                }
            }
            // 如果某段子数组中只包含一种元素，那么31行只会进入一次，且因为是第一个元素第一次进入，那么32行不会进入，那么tres不会得到更新
            if (tres != 110)
                res.push_back(tres);
            else 
                res.push_back(-1);
        }
        return res;
    }
};

下面来思考一下预处理前缀和数组的时候，为什么 i 从 1 开始，前缀和数组第 0 位留空。

首先我们假设前缀和数组就是从第 0 位开始，即 presum[i] 对应原数组 $[0,i]$ 位元素的和。会发生什么呢？
假设求从 0 开始计算的第 4 位到第 5 位子数组和，那么使用这样一个前缀和数组可得：
int res = presum[5] - presum[4 - 1];
似乎没有问题，好，那我现在求第 0 位到第 3 位子数组的和：
int res = presum[3] - presum[0 - 1];
数组下标出现负数，为了避免这种情况，只能多一次判断，不方便。

另外，在生成前缀和数组时，递推公式为：presum[i] = presum[i - 1] + nums[i].
问题是，这个递推公式无法适配所有情况。即，当 i 取 0 时，出现异常。
为了避免这个情况，只能把 presum[0] 拿出来预设为 nums[0] ，从数组第 1 项接着按照递推公式计算。不方便。

那么，为了方便地避免以上情况，我们决定将前缀和数组相对原数组向右偏移一位，用 presum[1] 表示原数组第 0 项， presum[2] 表示原数组第 [0,1] 项之和，将 presum[i] 表示为数组中 $[0,i-1]$ 所有数之和。

那么，如果求原数组从零计第 l 项到 r 项子数组之和，那么
int res = presum[r + 1] - presum[l + 1 - 1];
因为 presum[r] 表示的是 $[0, r-1]$ 项之和， presum[l] 表示 $[0,l-1]$ 项之和。
另外，如果求原数组从1计算第 l 项到 r 项子数组之和，可以直接：
int res = presum[r] - presum[l - 1];

原题链接： LeetCode 1906. 查询差绝对值的最小值