力扣每日一题 ---- 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};
    }
};


相关文章
【LeetCode-每日一题】-718. 最长重复子数组
【LeetCode-每日一题】-718. 最长重复子数组
|
5月前
|
C#
【力扣每日一题/04】57. 插入区间
【力扣每日一题/04】57. 插入区间
|
5月前
力扣每日一题 ---- 2918. 数组的最小相等和
力扣每日一题 ---- 2918. 数组的最小相等和
|
5月前
|
人工智能
每日一题 --- 2915. 和为目标值的最长子序列的长度
每日一题 --- 2915. 和为目标值的最长子序列的长度
|
5月前
|
测试技术
每日一题 --- 力扣318----最大单词长度乘积
每日一题 --- 力扣318----最大单词长度乘积
|
5月前
力扣每日一题 ---- 2906. 构造乘积矩阵
力扣每日一题 ---- 2906. 构造乘积矩阵
|
11月前
剑指offer_数组---旋转数组的最小数字
剑指offer_数组---旋转数组的最小数字
32 0
|
索引
力扣刷题记录——697. 数组的度、728. 自除数 、821. 字符的最短距离
力扣刷题记录——697. 数组的度、728. 自除数 、821. 字符的最短距离
力扣刷题记录——697. 数组的度、728. 自除数 、821. 字符的最短距离
|
存储 算法 Python
力扣刷题记录——190. 颠倒二进制位、191. 位1的个数、202. 快乐数
力扣刷题记录——190. 颠倒二进制位、191. 位1的个数、202. 快乐数
力扣刷题记录——190. 颠倒二进制位、191. 位1的个数、202. 快乐数