LeetCode 题解工作台
查询差绝对值的最小值
一个数组 a 的 差绝对值的最小值 定义为： 0 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值 。如果 a 中所有元素都 相同 ，那么差绝对值的最小值为 -1 。 比方说，数组 [5, 2 , 3 ,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
一个数组 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 <= 1051 <= nums[i] <= 1001 <= queries.length <= 2 * 1040 <= li < ri < nums.length
解题思路
方法一
class Solution:
def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
m, n = len(nums), len(queries)
pre_sum = [[0] * 101 for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, 101):
t = 1 if nums[i - 1] == j else 0
pre_sum[i][j] = pre_sum[i - 1][j] + t
ans = []
for i in range(n):
left, right = queries[i][0], queries[i][1] + 1
t = inf
last = -1
for j in range(1, 101):
if pre_sum[right][j] - pre_sum[left][j] > 0:
if last != -1:
t = min(t, j - last)
last = j
if t == inf:
t = -1
ans.append(t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on whether we precompute prefix counts or scan each query directly. Using prefix counts, each query takes O(100) time, leading to O(queries.length * 100). Space complexity is O(nums.length * 100) if storing prefix frequencies, or O(100) per query without prefix optimization. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask about handling repeated numbers and subarrays with identical elements.
- question_mark
Probe if candidates recognize that maximum nums[i] is 100 and can be used to optimize.
- question_mark
Check if the candidate can reduce O(n^2) comparisons by leveraging hash frequency arrays.
常见陷阱
外企场景- error
Attempting to compare all pairs in subarrays, leading to timeouts on large arrays.
- error
Forgetting that identical elements result in -1 for the minimum absolute difference.
- error
Ignoring that nums[i] is bounded at 100, missing the optimization opportunity.
进阶变体
外企场景- arrow_right_alt
Compute minimum absolute differences for dynamic updates on nums array.
- arrow_right_alt
Handle larger value ranges where hash frequency arrays are impractical.
- arrow_right_alt
Find the k-th smallest absolute difference instead of the minimum.