Medium

题目描述

给你一个长度为 n 的 0 索引 整数数组 nums，一个整数 indexDifference，和一个整数 valueDifference。

你的任务是找到两个在范围 [0, n - 1] 内的索引 i 和 j，它们满足以下条件：

  • abs(i - j) >= indexDifference，且
  • abs(nums[i] - nums[j]) >= valueDifference

返回一个整数数组 answer，其中 answer = [i, j] 如果存在这样的两个索引，否则 answer = [-1, -1]。如果有多种选择，返回其中任何一种即可。

注意：i 和 j 可以相等。

示例 1：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在这个例子中，可以选择 i = 0 和 j = 3。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4。
因此，[0,3] 是一个有效答案。
[3,0] 也是一个有效答案。

示例 2：

输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：在这个例子中，可以选择 i = 0 和 j = 0。
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0。
因此，[0,0] 是一个有效答案。
其他有效答案包括 [0,1]、[1,0] 和 [1,1]。

示例 3：

输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在这个例子中，可以证明无法找到满足两个条件的两个索引。
因此，返回 [-1,-1]。

约束：

  • 1 <= n == nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= indexDifference <= 10^5
  • 0 <= valueDifference <= 10^9

解题思路

这是一道关于双指针和优化搜索的题目。

思路分析：

朴素的解法是双重循环遍历所有可能的索引对，时间复杂度为O(n²)，对于大规模数据会超时。

优化思路： 关键观察是，对于当前索引i，我们只需要在满足索引差异条件的范围[0, i-indexDifference]内找到：

  1. 最小值对应的索引
  2. 最大值对应的索引

然后检查这两个候选索引是否满足值差异条件。

算法步骤：

  1. 从索引indexDifference开始遍历数组
  2. 对于每个索引i，维护前面范围[0, i-indexDifference]内的最小值索引和最大值索引
  3. 检查当前元素与这两个极值的差是否满足valueDifference条件
  4. 如果满足，立即返回结果；否则更新极值索引并继续

这种方法的核心是动态维护前缀最值，避免重复计算。时间复杂度优化到O(n)，空间复杂度O(1)。

**推荐解法：**使用双指针动态维护前缀最值的方法，既高效又简洁。

代码实现

class Solution {
public:
    vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
        int n = nums.size();
        int minIdx = 0, maxIdx = 0;
        
        for (int i = indexDifference; i < n; i++) {
            int j = i - indexDifference;
            
            // 更新最小值和最大值的索引
            if (nums[j] < nums[minIdx]) {
                minIdx = j;
            }
            if (nums[j] > nums[maxIdx]) {
                maxIdx = j;
            }
            
            // 检查是否满足值差异条件
            if (abs(nums[i] - nums[minIdx]) >= valueDifference) {
                return {i, minIdx};
            }
            if (abs(nums[i] - nums[maxIdx]) >= valueDifference) {
                return {i, maxIdx};
            }
        }
        
        return {-1, -1};
    }
};

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        n = len(nums)
        min_idx = 0
        max_idx = 0
        
        for i in range(indexDifference, n):
            j = i - indexDifference
            
            # 更新最小值和最大值的索引
            if nums[j] < nums[min_idx]:
                min_idx = j
            if nums[j] > nums[max_idx]:
                max_idx = j
            
            # 检查是否满足值差异条件
            if abs(nums[i] - nums[min_idx]) >= valueDifference:
                return [i, min_idx]
            if abs(nums[i] - nums[max_idx]) >= valueDifference:
                return [i, max_idx]
        
        return [-1, -1]

public class Solution {
    public int[] FindIndices(int[] nums, int indexDifference, int valueDifference) {
        int n = nums.Length;
        int minIdx = 0, maxIdx = 0;
        
        for (int i = indexDifference; i < n; i++) {
            int j = i - indexDifference;
            
            // 更新最小值和最大值的索引
            if (nums[j] < nums[minIdx]) {
                minIdx = j;
            }
            if (nums[j] > nums[maxIdx]) {
                maxIdx = j;
            }
            
            // 检查是否满足值差异条件
            if (Math.Abs(nums[i] - nums[minIdx]) >= valueDifference) {
                return new int[] {i, minIdx};
            }
            if (Math.Abs(nums[i] - nums[maxIdx]) >= valueDifference) {
                return new int[] {i, maxIdx};
            }
        }
        
        return new int[] {-1, -1};
    }
}

var findIndices = function(nums, indexDifference, valueDifference) {
    const n = nums.length;
    let minIdx = 0, maxIdx = 0;
    
    for (let i = indexDifference; i < n; i++) {
        const j = i - indexDifference;
        
        // 更新最小值和最大值的索引
        if (nums[j] < nums[minIdx]) {
            minIdx = j;
        }
        if (nums[j] > nums[maxIdx]) {
            maxIdx = j;
        }
        
        // 检查是否满足值差异条件
        if (Math.abs(nums[i] - nums[minIdx]) >= valueDifference) {
            return [i, minIdx];
        }
        if (Math.abs(nums[i] - nums[maxIdx]) >= valueDifference) {
            return [i, maxIdx];
        }
    }
    
    return [-1, -1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需要遍历一次数组，每次操作都是常数时间
空间复杂度O(1)只使用了常数个额外变量存储最值索引

相关题目