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

时间:2020-9-7 作者:admin


给你一个整数数组 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;
    }
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。