力扣2905. 找出满足差值条件的下标II

力扣2905. 找出满足差值条件的下标II

题目解析及思路

题目要求找到一对元素满足

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

从index开始枚举j，取i = j - index，维护<=i的区间中的最大值和最小值的下标，此时下标差距一定满足条件

下面两种情况成立时说明找到合法的一对下标了

• nums[max_idx] - nums[j] >= valueDifference
• nums[j] - nums[min_idx] >= valueDifference

代码

class Solution {
public:vector<int> findIndices(vector<int>& nums, int indexDifference, int valueDifference) {int max_idx = 0,min_idx = 0;for(int j=indexDifference;j<nums.size();j++){int i = j - indexDifference;//i对应的元素为最大值if(nums[i] > nums[max_idx])max_idx = i;//i对应的元素为最小值else if(nums[i] < nums[min_idx])min_idx = i;if(nums[max_idx] - nums[j] >= valueDifference)return {max_idx,j};if(nums[j] - nums[min_idx] >= valueDifference)return {min_idx,j};}return {-1,-1};}
};