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

给你一个整数数组 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

题解：

题目要求子数组中的任意两个元素之间的绝对差必须小于或者等于 limit，也就是说：这个子数组中的最大值-最小值的值要小于等于limit。因此我维护了两个优先队列，一个是大根堆，一个是小根堆，这样我们就能轻松获取到子数组中的最大值和最小值。接下来，就可以使用滑动窗口的模板了。需要注意的是，在窗口滑动时，要记得更新优先队列。

    public int longestSubarray(int[] nums, int limit) {
        if (nums == null || nums.length < 0) return 0;
        PriorityQueue<Integer> minQueue = new PriorityQueue<>(Comparator.naturalOrder()); //小根堆
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder()); //大根堆
        int n = nums.length;
        int left = 0;
        int right = 0;
        int ans = 0;
        while (right < n) {
            minQueue.add(nums[right]);
            maxQueue.add(nums[right]);
            while (maxQueue.peek() - minQueue.peek() > limit) {
                if (!maxQueue.isEmpty()) {
                    maxQueue.remove(nums[left]);
                }
                if (!minQueue.isEmpty()) {
                    minQueue.remove(nums[left]);
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;

        }
        return ans;
    }

还有另外一种数据结构：TreeMap。TreeMap 是 key 有序的哈希表，它是基于红黑树实现的。除此之外，它还提供了获取第一个元素(最小值)和最后一个元素(最大值)的函数，因此代码更加简洁。详细请参考这位大佬

    public int longestSubarray(int[] nums, int limit) {
        TreeMap<Integer, Integer> m = new TreeMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < nums.length) {
            m.put(nums[right], m.getOrDefault(nums[right], 0) + 1);
            while (m.lastKey() - m.firstKey() > limit) {
                m.put(nums[left], m.get(nums[left]) - 1);
                if (m.get(nums[left]) == 0) {
                    m.remove(nums[left]);
                }
                left ++;
            }
            res = Math.max(res, right - left + 1);
            right ++;
        }
        return res;
    }