Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
Example 1:
Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff |7-7| = 0 <= 4. Therefore, the size of the longest subarray is 2.
Example 2:
Input: nums = [10,1,2,4,7,2], limit = 5 Output: 4 Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.
Example 3:
Input: nums = [4,2,2,2,4,4,2,2], limit = 0 Output: 3
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= limit <= 10^9
绝对差不超过限制的最长连续子数组。题目即是题意，找一个最长的子数组，他们之间的最大值和最小值不能大于limit。我提供三种思路。
首先暴力解是O(n^2)的复杂度，用两个for loop不断地看，到底什么区间是满足条件的，然后记录一个最长的区间的长度即可。
其次是two pointer + treemap。这里我们利用了treemap里面元素是自然有序的特性。我们一开始初始化两个指针left和right，起点都是0。跑一下例子，比如我们把例子中的[8, 2, 4, 7]依次放进treemap，同时right指针会一步步往右移动。此时我们可以用treemap的firstEntry().getKey()和lastEntry().getKey()可以得到此时treemap中的最大值和最小值。如果最大值和最小值的差大于limit，则开始删减在左指针位置上的值，直到差值再次 <= limit为止。
注意最后为什么可以直接return j - i的差值，其实这时候j和i的下标这个区间不一定满足题意，但是j和i之间的距离是满足的。这里我们运用到了贪心的思想，只是在过程中截取到了j和i的一个合适的距离，但是当最大值和最小值的差大于limit的时候，我们其实是把j和i指针同时往右移动的。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int longestSubarray(int[] nums, int limit) { 3 int i = 0; 4 int j; 5 TreeMap<Integer, Integer> map = new TreeMap<>(); 6 for (j = 0; j < nums.length; j++) { 7 map.put(nums[j], map.getOrDefault(nums[j], 0) + 1); 8 if (map.lastEntry().getKey() - map.firstEntry().getKey() > limit) { 9 map.put(nums[i], map.get(nums[i]) - 1); 10 if (map.get(nums[i]) == 0) { 11 map.remove(nums[i]); 12 } 13 i++; 14 } 15 } 16 return j - i; 17 } 18 }
还有一种办法是sliding window + 单调queue。注意不是单调栈，而是单调queue。
我们维护一个单调递减queue maxQueue和一个单调递增queue minQueue，里面存的都是下标。maxQueue的首元素是当前遍历到的最大元素的下标，minQueue的首元素是当前遍历到的最小元素的下标。注意存元素也可以，但是存下标的好处是如果有重复元素，对下标是没有影响的。
同时我们需要两个指针start和end。一开始end往后走，当发现
- maxQueue不为空且maxQueue的最后一个元素小于当前元素nums[end]了，则不断往外poll元素，直到整个maxQueue变回降序
- minQueue不为空且minQueue的最后一个元素大于当前元素nums[end]了，则不断往外poll元素，直到整个minQueue变回升序
此时再判断，如果两个queue都不为空但是两个queue里的最后一个元素（一个是最大值，一个是最小值）的差值大于limit了，则开始左移start指针，左移的同时，如果两个queue里有任何元素的下标<= start，则往外poll，因为不需要了。这里也是存下标的另一个好处，因为下标一定是有序被放进两个queue的，所以如果大于limit了，你是需要从最一开始的start指针那里开始检查的。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int longestSubarray(int[] nums, int limit) { 3 // all the elements are decending 4 Deque<Integer> maxQueue = new ArrayDeque<>(); 5 // all the elements are increasing 6 Deque<Integer> minQueue = new ArrayDeque<>(); 7 int res = 0; 8 int start = 0; 9 for (int end = 0; end < nums.length; end++) { 10 while (!maxQueue.isEmpty() && nums[maxQueue.peekLast()] < nums[end]) { 11 maxQueue.pollLast(); 12 } 13 maxQueue.add(end); 14 while (!minQueue.isEmpty() && nums[minQueue.peekLast()] > nums[end]) { 15 minQueue.pollLast(); 16 } 17 minQueue.add(end); 18 19 while (!maxQueue.isEmpty() && !minQueue.isEmpty() 20 && nums[maxQueue.peekFirst()] - nums[minQueue.peekFirst()] > limit) { 21 if (maxQueue.peekFirst() <= start) { 22 maxQueue.pollFirst(); 23 } 24 if (minQueue.peekFirst() <= start) { 25 minQueue.pollFirst(); 26 } 27 start++; 28 } 29 res = Math.max(res, end - start + 1); 30 } 31 return res; 32 } 33 }