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

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。 如果不存在满足条件的子数组，则返回 0

思路分析

常规滑动窗口题，比较值得注意是如何维护一个数据结构保证每次添加数据之后的数据结构依然是有序的，能让我们取其中最大值和最小值，来进行判断新添加的数据是否能够在limit里面。

class Solution {
    public int longestSubarray(int[] nums, int limit) {
      
 int left = 0, right = 0, max = 0;
    TreeSet<Integer> treeSet = new TreeSet<>(
       (a, b) -> {
        if (nums[a] == nums[b]) return a - b; 
        return Integer.compare(nums[a], nums[b]);
    } );
    while (right < nums.length) {
        treeSet.add(right); 

        while (!treeSet.isEmpty() && (nums[treeSet.last()] - nums[treeSet.first()]) > limit) {
            treeSet.remove(left++); 
        }

        max = Math.max(max, right - left + 1); 
        right++; 
    }
    return max;
    }
}

几种有序数据结构实现取最大值和最小值总结

TreeSet实现

 TreeSet<Integer> treeSet = new TreeSet<>(
       (a, b) -> {
        if (nums[a] == nums[b]) return a - b; 
        return Integer.compare(nums[a], nums[b]);
    } );
  • if (nums[a] == nums[b]) return a - b; 保证相同的数据时，能够通过索引来进行大小判断，不会被判相同元素

Compare方法比较作为参数给出的两个整数值(x，y)，如果(x == y)则返回零，如果(x <y)则返回小于零的值，如果(x> y)，则返回大于零的值。

同时维护一个最大值双端队列和最小值双端队列

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> queMax = new LinkedList<Integer>();
        Deque<Integer> queMin = new LinkedList<Integer>();
        int n = nums.length;
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            while (!queMax.isEmpty() && queMax.peekLast() < nums[right]) {
                queMax.pollLast();
            }
            while (!queMin.isEmpty() && queMin.peekLast() > nums[right]) {
                queMin.pollLast();
            }
            queMax.offerLast(nums[right]);
            queMin.offerLast(nums[right]);
            while (!queMax.isEmpty() && !queMin.isEmpty() && queMax.peekFirst() - queMin.peekFirst() > limit) {
                if (nums[left] == queMin.peekFirst()) {
                    queMin.pollFirst();
                }
                if (nums[left] == queMax.peekFirst()) {
                    queMax.pollFirst();
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
}
  • offerLast 将指定元素添加到双端队列的末尾
  • peekLast 获取双端队列的最后一个元素
  • pollLast 移除并返回双端队列的最后一个元素
  • peekFirst 获取双端队列的第一个元素
  • pollFrist 移除并返回双端队列的第一个元素

通过判断最后一个元素是否大于和小于当前元素来维护队列

数组实现

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        // l, r 是 nums 的左右指针, len 是 nums 的长度, minL 和 minR 是最小值区间的左右指针, maxL 和 maxR 是最大值区间的左右指针.
        int l = 0, r = 0, len = nums.length, minL = 0, minR = -1, maxL = len, maxR = len - 1;
        // 这个数组用来记录最小值和最大值
        int[] ascending = new int[len];
        // 开始遍历 nums
        while (r < len) {
            // 每一次遍历到的数字, 并更新子集右指针
            int n = nums[r++];
            // 如果遍历到的数字在最小值区间内, 就收缩最小值区间
            while (minR >= minL && n < ascending[minR]) minR--;
            // 如果遍历到的数字在最大值区间内, 就收缩最大值区间
            while (maxR >= maxL && n > ascending[maxL]) maxL++;
            // 拓展最小值和最大值区间
            ascending[++minR] = ascending[--maxL] = n;
            // 判断子集长度是否符合 limit 的要求, 如果不符合要求, 就收缩子集
            if (ascending[maxR] - ascending[minL] > limit) {
                // 开始收缩子集, 使子集左指针右移
                // 如果子集左指针是最小值, 那么最小值将被移除, 所以更新存储最小值的区间
                if (nums[l] == ascending[minL]) minL++;
                // 如果子集左指针是最大值, 那么最大值将被移除, 所以更新存储最大值的区间
                if (nums[l++] == ascending[maxR]) maxR--;
            }
        }
        // 返回结果
        return r - l;
    }
}

总结

动态获取最大值和最小值是很常用的手段