Question

2903. 找出满足差值条件的下标 I

English Version

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出  2 个满足下述所有条件的下标 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]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。

 

提示：

• 1 <= n == nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= indexDifference <= 100
• 0 <= valueDifference <= 50

解法

方法一：双指针 + 维护最大最小值

我们用两个指针 $i$ 和 $j$ 来维护一个间隔为 $indexDifference$ 的滑动窗口，其中指针 $j$ 和 $i$ 分别指向窗口的左右边界。初始时 $i$ 指向 $indexDifference$，而 $j$ 指向 $0$。

我们用 $mi$ 和 $mx$ 来维护指针 $j$ 左侧区间的最小值下标和最大值下标。

当指针 $i$ 向右移动时，我们需要更新 $mi$ 和 $mx$。如果 $nums[j] < nums[mi]$，则 $mi$ 更新为 $j$；如果 $nums[j] > nums[mx]$，则 $mx$ 更新为 $j$。更新完 $mi$ 和 $mx$ 后，我们就可以判断是否找到了满足条件的下标对。如果 $nums[i] - nums[mi] \geq valueDifference$，则找到了满足条件的下标对 $[mi, i]$；如果 $nums[mx] - nums[i] \geq valueDifference$，则找到了满足条件的下标对 $[mx, i]$。

如果指针 $i$ 移动到了数组的末尾，说明没有找到满足条件的下标对，返回 $[-1, -1]$。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

class Solution:
  def findIndices(
    self, nums: List[int], indexDifference: int, valueDifference: int
  ) -> List[int]:
    mi = mx = 0
    for i in range(indexDifference, len(nums)):
      j = i - indexDifference
      if nums[j] < nums[mi]:
        mi = j
      if nums[j] > nums[mx]:
        mx = j
      if nums[i] - nums[mi] >= valueDifference:
        return [mi, i]
      if nums[mx] - nums[i] >= valueDifference:
        return [mx, i]
    return [-1, -1]

class Solution {
  public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
    int mi = 0;
    int mx = 0;
    for (int i = indexDifference; i < nums.length; ++i) {
      int j = i - indexDifference;
      if (nums[j] < nums[mi]) {
        mi = j;
      }
      if (nums[j] > nums[mx]) {
        mx = j;
      }
      if (nums[i] - nums[mi] >= valueDifference) {
        return new int[] {mi, i};
      }
      if (nums[mx] - nums[i] >= valueDifference) {
        return new int[] {mx, i};
      }
    }
    return new int[] {-1, -1};
  }
}

class Solution {
public:
  vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {
    int mi = 0, mx = 0;
    for (int i = indexDifference; i < nums.size(); ++i) {
      int j = i - indexDifference;
      if (nums[j] < nums[mi]) {
        mi = j;
      }
      if (nums[j] > nums[mx]) {
        mx = j;
      }
      if (nums[i] - nums[mi] >= valueDifference) {
        return {mi, i};
      }
      if (nums[mx] - nums[i] >= valueDifference) {
        return {mx, i};
      }
    }
    return {-1, -1};
  }
};

func findIndices(nums []int, indexDifference int, valueDifference int) []int {
  mi, mx := 0, 0
  for i := indexDifference; i < len(nums); i++ {
    j := i - indexDifference
    if nums[j] < nums[mi] {
      mi = j
    }
    if nums[j] > nums[mx] {
      mx = j
    }
    if nums[i]-nums[mi] >= valueDifference {
      return []int{mi, i}
    }
    if nums[mx]-nums[i] >= valueDifference {
      return []int{mx, i}
    }
  }
  return []int{-1, -1}
}

function findIndices(nums: number[], indexDifference: number, valueDifference: number): number[] {
  let [mi, mx] = [0, 0];
  for (let i = indexDifference; i < nums.length; ++i) {
    const j = i - indexDifference;
    if (nums[j] < nums[mi]) {
      mi = j;
    }
    if (nums[j] > nums[mx]) {
      mx = j;
    }
    if (nums[i] - nums[mi] >= valueDifference) {
      return [mi, i];
    }
    if (nums[mx] - nums[i] >= valueDifference) {
      return [mx, i];
    }
  }
  return [-1, -1];
}

impl Solution {
  pub fn find_indices(nums: Vec<i32>, index_difference: i32, value_difference: i32) -> Vec<i32> {
    let index_difference = index_difference as usize;
    let mut mi = 0;
    let mut mx = 0;

    for i in index_difference..nums.len() {
      let j = i - index_difference;

      if nums[j] < nums[mi] {
        mi = j;
      }

      if nums[j] > nums[mx] {
        mx = j;
      }

      if nums[i] - nums[mi] >= value_difference {
        return vec![mi as i32, i as i32];
      }

      if nums[mx] - nums[i] >= value_difference {
        return vec![mx as i32, i as i32];
      }
    }

    vec![-1, -1]
  }
}