题目
给你一个整数数组 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时，left右移，同时最小堆和最大堆中删除nums[left]。
public int longestSubarray(int[] nums, int limit) {
int left=0,right=0,maxLen=0;
PriorityQueue<Integer> minHeap=new PriorityQueue<>();
PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b){
return b-a;
}
});
while(right<nums.length){
maxHeap.offer(nums[right]);
minHeap.offer(nums[right]);
while(maxHeap.peek()-minHeap.peek()>limit){
maxHeap.remove(nums[left]);
minHeap.remove(nums[left]);
left++;
}
right++;
if(maxLen<right-left) maxLen=right-left;
}
return maxLen;
}
滑动窗口+TreeMap
TreeMap内的元素是按键值排序的(默认为升序)，可以将窗口内的元素作为键值放入TreeMap中，这样也可以动态获取最值。
public int longestSubarray(int[] nums, int limit) {
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
int left = 0, right = 0, maxLen=0;
while (right < nums.length) {
treeMap.compute(nums[right++], (k, v) -> v == null ? 1 : v + 1);
//treeMap.lastKey()和treeMap.firstKey()分别是窗口中的最大值和最小值
while(treeMap.lastKey() - treeMap.firstKey() > limit) {
treeMap.compute(nums[left++], (k, v) -> v == 1 ? null : v - 1);
}
if(maxLen<right-left) maxLen=right-left;
}
return maxLen;
}