找出满足差值条件的下标 II
难度:
标签:
题目描述
You are given a 0-indexed integer array nums having length n, an integer indexDifference, and an integer valueDifference.
Your task is to find two indices i and j, both in the range [0, n - 1], that satisfy the following conditions:
abs(i - j) >= indexDifference, andabs(nums[i] - nums[j]) >= valueDifference
Return an integer array answer, where answer = [i, j] if there are two such indices, and answer = [-1, -1] otherwise. If there are multiple choices for the two indices, return any of them.
Note: i and j may be equal.
Example 1:
Input: nums = [5,1,4,1], indexDifference = 2, valueDifference = 4 Output: [0,3] Explanation: In this example, i = 0 and j = 3 can be selected. abs(0 - 3) >= 2 and abs(nums[0] - nums[3]) >= 4. Hence, a valid answer is [0,3]. [3,0] is also a valid answer.
Example 2:
Input: nums = [2,1], indexDifference = 0, valueDifference = 0 Output: [0,0] Explanation: In this example, i = 0 and j = 0 can be selected. abs(0 - 0) >= 0 and abs(nums[0] - nums[0]) >= 0. Hence, a valid answer is [0,0]. Other valid answers are [0,1], [1,0], and [1,1].
Example 3:
Input: nums = [1,2,3], indexDifference = 2, valueDifference = 4 Output: [-1,-1] Explanation: In this example, it can be shown that it is impossible to find two indices that satisfy both conditions. Hence, [-1,-1] is returned.
Constraints:
1 <= n == nums.length <= 1050 <= nums[i] <= 1090 <= indexDifference <= 1050 <= valueDifference <= 109
代码结果
运行时间: 60 ms, 内存: 30.5 MB
/*
* 题目思路：
* 1. 使用 Java Stream 进行数组的遍历，使用两层流处理，外层流为 i，内层流为 j。
* 2. 对于每个 i 和 j，检查是否满足 abs(i - j) >= indexDifference 和 abs(nums[i] - nums[j]) >= valueDifference 的条件。
* 3. 如果满足条件，则返回 [i, j]。
* 4. 如果没有找到满足条件的对，返回 [-1, -1]。
*/
import java.util.stream.IntStream;
public class Solution {
public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
int n = nums.length;
return IntStream.range(0, n)
.flatMap(i -> IntStream.range(0, n)
.filter(j -> Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference)
.mapToObj(j -> new int[]{i, j}))
.findFirst()
.orElse(new int[]{-1, -1});
}
}
解释
方法:
此题解采用了滑动窗口的方法来寻找满足条件的下标i和j。首先定义两个变量mxi和mni，分别用于记录当前窗口中最大和最小元素的下标。窗口的大小由indexDifference参数确定，即窗口内任两点的下标差至少为indexDifference。然后遍历数组，对于每个元素nums[j]，计算其与indexDifference之前的元素的最大值和最小值的差。如果任一差值满足valueDifference，则返回对应的下标。如果遍历完成后没有找到满足条件的下标对，则返回[-1, -1]。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到使用滑动窗口的大小由`indexDifference`参数决定，具体是如何应用这个参数来设置窗口大小的？
▷🦆
在更新最大和最小下标`mxi`和`mni`时，为什么只考虑了当前窗口开始下标`i`的元素，而没有遍历整个窗口来确定最大或最小值？
▷🦆
题解中的滑动窗口策略似乎没有处理窗口内最大或最小值下标失效的情况（即当这些下标超出当前考虑的窗口时）。这种情况该如何处理？
▷