找出满足差值条件的下标 II

难度: Medium

给你一个下标从 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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= indexDifference <= 10⁵
0 <= valueDifference <= 10⁹

Submission

运行时间: 60 ms

内存: 30.5 MB

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

Explain

此题解采用了滑动窗口的方法来寻找满足条件的下标i和j。首先定义两个变量mxi和mni，分别用于记录当前窗口中最大和最小元素的下标。窗口的大小由indexDifference参数确定，即窗口内任两点的下标差至少为indexDifference。然后遍历数组，对于每个元素nums[j]，计算其与indexDifference之前的元素的最大值和最小值的差。如果任一差值满足valueDifference，则返回对应的下标。如果遍历完成后没有找到满足条件的下标对，则返回[-1, -1]。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
        mxi = mni = 0  # 初始化最大和最小元素的下标
        for j in range(indexDifference, len(nums)):
            i = j - indexDifference  # 计算当前窗口的起始下标
            # 更新当前窗口的最大和最小下标
            if nums[i] > nums[mxi]:
                mxi = i 
            elif nums[i] < nums[mni]:
                mni = i 
            # 检查是否满足条件
            if nums[mxi] - nums[j] >= valueDifference:
                return [mxi, j]
            if nums[j] - nums[mni] >= valueDifference:
                return [mni, j]
        return [-1, -1]  # 如果没有找到满足条件的下标对

Explore

在题解中，滑动窗口的大小实际上是通过`indexDifference`来间接确定的。窗口内的元素数量并不是直接等于`indexDifference`，而是通过确保`i`和`j`之间的索引差至少为`indexDifference`来维持窗口的逻辑。这意味着窗口的实际宽度（即包含的元素数量）可以根据数组的遍历动态调整，但始终保证任何被比较的两个元素的下标差不小于`indexDifference`。这种设置使得算法能够在遍历数组时，始终保持一个满足条件的动态窗口，用于检查是否有两个元素满足给定的值差条件。

题解采用了一种贪心策略，只在每次迭代时检查新加入窗口的元素（即`i`位置的元素），而不重新遍历整个窗口。这种方法假设在之前的步骤中，窗口内的最大值和最小值已经被正确更新。因此，只需考虑新元素是否会影响当前的最大或最小记录即可。这样可以大幅减少计算量，提高效率。然而，这种方法在实际代码实现中存在逻辑漏洞，因为当最大值或最小值离开窗口时应重新计算窗口内的最大或最小值，而题解中的实现并未处理这一点。

正确地处理窗口内最大值或最小值下标失效的问题是滑动窗口算法的关键部分。在题解中的实现方式中，如果最大或最小值的下标`mxi`或`mni`超过了当前窗口的边界，应当重新扫描当前窗口以确定新的最大或最小值。更高效的方法是使用数据结构如双端队列（Deque），它可以在每次窗口滑动时高效地添加新元素并移除旧元素，同时维护窗口内的最大或最小值的下标。这样可以在每次窗口更新时保持常数时间复杂度的更新操作，而不需要重新扫描整个窗口。