LEETCODE 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit 解题思路分析

题目大意:

绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组,则返回 0 。

示例 1:

输入:nums = [8,2,4,7], limit = 4
输出:2
解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4. [8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4. [2,4] 最大绝对差 |2-4| = 2 <= 4. [2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此,满足题意的最长子数组的长度为 2 。

示例 2:

输入:nums = [10,1,2,4,7,2], limit = 5
输出:4
解释:满足题意的最长子数组是 [2,4,7,2],其最大绝对差 |2-7| = 5 <= 5 。

示例 3:

输入:nums = [4,2,2,2,4,4,2,2], limit = 0
输出:3

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1438

解题思路分析:

看到这种求连续区间(子数组)的题目,我们要联想到尝试使用双指针来解题。对于本题,如果一个区间内任意两个元素差的绝对值小于等于limit,则说明该区间内的最大值与最小值的差要小于等于limit。因此我们使用左右两个指针分别代表区间的两个边界,初始时左右边界均在数组的最左段(下标为0处)。我们开始尝试移动右指针,右指针指向的当前数字为区间内新被加入进来的元素,我们用该元素去更新区间内的最大值与最小值,同时记录下该最大值或者最小值所在的下标位置。此时,如果最大值与最小值之差小于等于limit,说明当前区间为合理区间,使用当前区间长度更新全局最长长度。

反之如果当前区间内最大值与最小值差大于limit,说明当前右指针指向的数字加入区间后,要么更新了区间内最大值,要么更新了区间内最小值,从而使得区间从合理变为不合理。此时如果当前数字是区间最大值的话,我们就将区间左指针移动到原区间最小值的后一位。同理如果当前数字是区间最小值的话,我们就将区间左指针移动到原区间最大值的后一位。这样就能保证区间重新变为合理,但是这样做存在一个问题,新的区间内我们移除了原先的最大值(或者最小值)后,我们无法马上取得当前区间内新的最大值或者最小值,因此为了计算方便,我们可以牺牲一些效率,直接将左右指针都移动至原区间内最大值(或者如果当前右指针是最大值的话,就是最小值)的后一位即可。接下来再开始移动右指针,重复上述过程,直到右指针到达数组末尾为止。

实现代码:

public int longestSubarray(int[] nums, int limit) {
    // 左右指针
    int left=0, right=0;
    // 区间内最大值与最小值
    int max=nums[0], min=nums[0];
    // 区间内最大值与最小值所在下标
    int maxIndex=0, minIndex=0;
    // 返回结果(最长合理区间)
    int res=1;
    while(right<nums.length){
        // 如果右指针是区间最大值
        if(nums[right]>=max){
            // 更新区间最大值以及下标
            max=nums[right];
            maxIndex=right;
        }
        // 如果右指针是区间最小值
        if(nums[right]<=min){
            // 更新区间最小值以及下标
            min=nums[right];
            minIndex=right;
        }
        // 区间内最大值与最小值差小于等于limit
        if(max-min<=limit){
            // 当前为合理区间,更新最大合理区间
            res=Math.max(res, right-left+1);
            right++; // 右指针加一
        }else{ // 区间内最大值与最小值差大于limit
            // 如果右指针是区间最大值
            if(nums[right]==max){
                // 左右指针都重置至原区间最小值下标加一位置
                left=minIndex+1;
                right=minIndex+1;
                // 区间最大值与最小值更新为当前指针位置的数字
                if(minIndex+1<nums.length){
                    max=nums[minIndex+1];
                    min=nums[minIndex+1];
                }
                // 更新区间最大值与最小值的下标
                maxIndex=minIndex+1;
                minIndex=minIndex+1;
            }else if(nums[right]==min){
                left=maxIndex+1;
                right=maxIndex+1;
                if(maxIndex+1<nums.length){
                    max=nums[maxIndex+1];
                    min=nums[maxIndex+1];
                }
                minIndex=maxIndex+1;
                maxIndex=maxIndex+1;
            }
        }
    }
    return res;
}

本题解法执行时间4ms。

Runtime: 4 ms, faster than 98.77% of Java online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.

Memory Usage: 48.3 MB, less than 100.00% of Java online submissions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1438-longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。