Medium

题目描述

数组 a 的 最小绝对差值 定义为：|a[i] - a[j]| 的最小值，其中 0 <= i < j < a.length 且 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（包含）之间的元素。

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

子数组 是数组中元素的连续序列。

|x| 的值定义为：

  • 如果 x >= 0，则 |x| = x
  • 如果 x < 0，则 |x| = -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]

提示：

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

解题思路

这道题的关键在于注意到数组元素的范围只有1到100，这个限制提示我们可以使用前缀和的思想来优化。

核心思路：

由于元素值范围很小（1≤nums[i]≤100），我们可以为每个可能的值维护一个前缀和数组，记录从数组开始到每个位置，每个值出现的次数。这样对于任意查询区间[l,r]，我们能在O(1)时间内判断某个值是否在该区间出现。

具体步骤：

  1. 构建前缀和数组：prefixCount[i][val] 表示在前i个元素中，值为val的元素出现次数
  2. 对于每个查询[l,r]，通过前缀和快速得到区间内每个值的出现次数
  3. 收集区间内所有出现的不同值，如果只有一种值则返回-1
  4. 对所有出现的值进行排序，计算相邻值之间的最小差值

时间复杂度优化： 由于值的范围很小，我们可以在O(100)时间内遍历所有可能的值，而不需要对实际出现的值进行排序，这进一步优化了算法效率。

这种方法充分利用了题目的约束条件，将原本可能需要O(n)处理每个查询的问题，优化到了O(100)的常数时间。

代码实现

class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        // 前缀和数组，prefixCount[i][val] 表示前i个元素中值为val的个数
        vector<vector<int>> prefixCount(n + 1, vector<int>(101, 0));
        
        // 构建前缀和
        for (int i = 0; i < n; i++) {
            for (int val = 1; val <= 100; val++) {
                prefixCount[i + 1][val] = prefixCount[i][val];
            }
            prefixCount[i + 1][nums[i]]++;
        }
        
        vector<int> result;
        for (auto& query : queries) {
            int l = query[0], r = query[1];
            vector<int> values;
            
            // 找出区间[l,r]中出现的所有不同值
            for (int val = 1; val <= 100; val++) {
                int count = prefixCount[r + 1][val] - prefixCount[l][val];
                if (count > 0) {
                    values.push_back(val);
                }
            }
            
            // 如果只有一种值，返回-1
            if (values.size() < 2) {
                result.push_back(-1);
                continue;
            }
            
            // 找最小差值
            int minDiff = INT_MAX;
            for (int i = 1; i < values.size(); i++) {
                minDiff = min(minDiff, values[i] - values[i-1]);
            }
            result.push_back(minDiff);
        }
        
        return result;
    }
};

class Solution:
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        # 前缀和数组，prefix_count[i][val] 表示前i个元素中值为val的个数
        prefix_count = [[0] * 101 for _ in range(n + 1)]
        
        # 构建前缀和
        for i in range(n):
            for val in range(1, 101):
                prefix_count[i + 1][val] = prefix_count[i][val]
            prefix_count[i + 1][nums[i]] += 1
        
        result = []
        for l, r in queries:
            values = []
            
            # 找出区间[l,r]中出现的所有不同值
            for val in range(1, 101):
                count = prefix_count[r + 1][val] - prefix_count[l][val]
                if count > 0:
                    values.append(val)
            
            # 如果只有一种值，返回-1
            if len(values) < 2:
                result.append(-1)
                continue
            
            # 找最小差值
            min_diff = float('inf')
            for i in range(1, len(values)):
                min_diff = min(min_diff, values[i] - values[i-1])
            result.append(min_diff)
        
        return result

public class Solution {
    public int[] MinDifference(int[] nums, int[][] queries) {
        int n = nums.Length;
        // 前缀和数组，prefixCount[i][val] 表示前i个元素中值为val的个数
        int[,] prefixCount = new int[n + 1, 101];
        
        // 构建前缀和
        for (int i = 0; i < n; i++) {
            for (int val = 1; val <= 100; val++) {
                prefixCount[i + 1, val] = prefixCount[i, val];
            }
            prefixCount[i + 1, nums[i]]++;
        }
        
        int[] result = new int[queries.Length];
        for (int q = 0; q < queries.Length; q++) {
            int l = queries[q][0], r = queries[q][1];
            List<int> values = new List<int>();
            
            // 找出区间[l,r]中出现的所有不同值
            for (int val = 1; val <= 100; val++) {
                int count = prefixCount[r + 1, val] - prefixCount[l, val];
                if (count > 0) {
                    values.Add(val);
                }
            }
            
            // 如果只有一种值，返回-1
            if (values.Count < 2) {
                result[q] = -1;
                continue;
            }
            
            // 找最小差值
            int minDiff = int.MaxValue;
            for (int i = 1; i < values.Count; i++) {
                minDiff = Math.Min(minDiff, values[i] - values[i-1]);
            }
            result[q] = minDiff;
        }
        
        return result;
    }
}

var minDifference = function(nums, queries) {
    const n = nums.length;
    // 前缀和数组，prefixCount[i][val] 表示前i个元素中值为val的个数
    const prefixCount = Array(n + 1).fill().map(() => Array(101).fill(0));
    
    // 构建前缀和
    for (let i = 0; i < n; i++) {
        for (let val = 1; val <= 100; val++) {
            prefixCount[i + 1][val] = prefixCount[i][val];
        }
        prefixCount[i + 1][nums[i]]++;
    }
    
    const result = [];
    for (const [l, r] of queries) {
        const values = [];
        
        // 找出区间[l,r]中出现的所有不同值
        for (let val = 1; val <= 100; val++) {
            const count = prefixCount[r + 1][val] - prefixCount[l][val];
            if (count > 0) {
                values.push(val);
            }
        }
        
        // 如果只有一种值，返回-1
        if (values.length < 2) {
            result.push(-1);
            continue;
        }
        
        // 找最小差值
        let minDiff = Number.MAX_SAFE_INTEGER;
        for (let i = 1; i < values.length; i++) {
            minDiff = Math.min(minDiff, values[i] - values[i-1]);
        }
        result.push(minDiff);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × 100 + q × 100)构建前缀和需要O(n×100)，处理q个查询每个需要O(100)
空间复杂度O(n × 100)前缀和数组的空间开销

其中 n 是数组长度，q 是查询次数。由于元素值范围固定为1-100，所以100可以视为常数。