力扣每日一题 ---- 2905. 找出满足差值条件的下标 II

简介: 力扣每日一题 ---- 2905. 找出满足差值条件的下标 II

7.png8.png

这道题带有绝对值差的题,一看就是双指针的题,并且还带有两个限制,那么我们的做法就是

固定一个条件,维护一个条件

本题还用到了一个贪心思路,会介绍到

那我们怎么固定一个条件,维护一个条件?

并且固定哪一个条件,维护哪一个条件更好呢?

1.如果是固定大小,维护下标,那么我们需要先排序,才能使用双指针

2.如果是固定下标,维护大小,那么我们不需要排序,那么时间复杂度就比第一种好,选第二种

这里我们怎么维护大小呢?(如果是枚举j,固定j下标,那么我们要算出i和i之前有效范围内最大最小值,如果前面有最大最小值符合,那么我们就符合)

那么怎么说明只要最大最小值符合我们就符合呢,因为abs( ? -  nums[j]) 要想val最大,那么需要?最大或最小才能使的差值最大(这里就是一个贪心)

我们枚举下标j,那么可以知道 i <= j - indexDifference,算出i,然后i , j就像滑动窗口一样固定住

左边和右边了,然后记录i 和 i之前数的最大最小值,因为i下标和i下标之前的数一定是符合我们的下标条件了(那么这就是我们固定住了第一个条件,维护大小值),因为我们知道了下标就知道了

数,那么我们就维护最大最小值的下标

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


相关文章
|
6月前
|
C++ 索引
leetcode-724:寻找数组的中心下标
leetcode-724:寻找数组的中心下标
34 0
【Leetcode -724.寻找数组的中心下标 -728.自除数】
【Leetcode -724.寻找数组的中心下标 -728.自除数】
65 0
|
11月前
|
算法
【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置
【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置
|
6月前
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
|
3月前
|
算法 Java
LeetCode第28题找出字符串中第一个匹配项的下标
这篇文章介绍了LeetCode第28题"找出字符串中第一个匹配项的下标"的两种解法:暴力解法和KMP算法,并解释了KMP算法通过构建前缀表来提高字符串搜索的效率。
LeetCode第28题找出字符串中第一个匹配项的下标
|
5月前
|
算法 Java
力扣经典150题第二十三题:找出字符串中第一个匹配项的下标
力扣经典150题第二十三题:找出字符串中第一个匹配项的下标
29 0
|
5月前
leetcode题解:28.找出字符串中第一个匹配项的下标
leetcode题解:28.找出字符串中第一个匹配项的下标
26 0
|
5月前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
5月前
|
算法 Java Go
【经典算法】LeetCode28 找出字符串中第一个匹配项的下标(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode28 找出字符串中第一个匹配项的下标(Java/C/Python3实现含注释说明,Easy)
45 0
|
6月前
【力扣】28. 找出字符串中第一个匹配项的下标
【力扣】28. 找出字符串中第一个匹配项的下标