LeetCode数组类题解( 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度)

￡神魔★判官ぃ 2022-12-04 07:49 60阅读 0赞

# 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度 #

该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。如果不存在满足条件的子数组，则返回 0 。

*  示例 ：  
    输入：nums = \[10,1,2,4,7,2\], limit = 5  
    输出：4  
    解释：满足题意的最长子数组是 \[2,4,7,2\]，其最大绝对差 |2-7| = 5 <= 5 。
 *  示例 2：  
    输入：nums = \[4,2,2,2,4,4,2,2\], limit = 0  
    输出：3
 *  **分析**：

> 连续子数组，组数组中最大值 - 最小值 <= limit  
> 设置队列中元素左边界i和右边界j，找出队列中的最大值max和最小值min（每次修改队列后都需要更改最大值最小值 ===> 考虑使用队列，规定队列的排序方式）
> 
>  *  如果新增元素与最大值最小值的差均符合条件，则右边界j右移，更新子数组的最长长度
>  *  如果不符合条件，左边界向右移动

### 代码： ###

/** * 连续，子数组中最大值 - 最小值 <= limit * 设置队列元素的左边界i和右边界j * 找出这个队列中的最大值最小值 * 如果新增元素与最大值最小值的差均符合条件，则右边界j右移 * 如果不符合条件，左边界向右移动，同时更新最大值或最小值 * * @param nums * @param limit * @return */
        public static int longestSubarray2(int[] nums, int limit) { 
            if (nums.length == 0 || nums.length == 1) return nums.length;
            //i最左侧，j右侧元素，res结果
            int i = 0, j = 0, res = 1;
            int n = nums.length;
            PriorityQueue<Integer> min = new PriorityQueue<>();//获取最小值
            PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());//规定队列排序的方式，获取最大值
            while (i < n && j < n) { 
                if (min.size() == 0) { 
                    min.add(nums[j]);
                    max.add(nums[j]);
                    j++;
                    continue;
                }
                //最大值 - 当前值 <= limit&& 最大值 - 当前值 <=limit
                if(Math.abs(nums[j]- min.peek() )<=limit && Math.abs(max.peek() - nums[j])<=limit){ 
                    min.add(nums[j]);
                    max.add(nums[j]);
                    res = Math.max(res,j-i+1);
                    j++;
                }else { 
                    min.remove(nums[i]);
                    max.remove(nums[i]);
                    i++;
                }
            }
    
            return res;
        }