1438. 絕對差不超過限制的最長連續(xù)子數(shù)組

給你一個整數(shù)數(shù)組 nums ，和一個表示限制的整數(shù) limit，請你返回最長連續(xù)子數(shù)組的長度，該子數(shù)組中的任意兩個元素之間的絕對差必須小于或者等于 limit 。
如果不存在滿足條件的子數(shù)組，則返回 0 。

示例 1：

輸入：nums = [8,2,4,7], limit = 4
輸出：2 
解釋：所有子數(shù)組如下：
[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. 
因此，滿足題意的最長子數(shù)組的長度為 2 。

示例 2：

輸入：nums = [10,1,2,4,7,2], limit = 5
輸出：4 
解釋：滿足題意的最長子數(shù)組是 [2,4,7,2]，其最大絕對差 |2-7| = 5 <= 5 。

示例 3：

輸入：nums = [4,2,2,2,4,4,2,2], limit = 0
輸出：3

題解：

題目要求子數(shù)組中的任意兩個元素之間的絕對差必須小于或者等于 limit，也就是說：這個子數(shù)組中的最大值-最小值的值要小于等于limit。因此我維護了兩個優(yōu)先隊列，一個是大根堆，一個是小根堆，這樣我們就能輕松獲取到子數(shù)組中的最大值和最小值。接下來，就可以使用滑動窗口的模板了。需要注意的是，在窗口滑動時，要記得更新優(yōu)先隊列。

    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;
    }

還有另外一種數(shù)據(jù)結構：TreeMap。TreeMap 是 key 有序的哈希表，它是基于紅黑樹實現(xiàn)的。除此之外，它還提供了獲取第一個元素(最小值)和最后一個元素(最大值)的函數(shù)，因此代碼更加簡潔。詳細請參考這位大佬

    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;
    }