05 August 2008
给一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：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 。
用第二种办法
枚举每一个位置作为右端点，找到其对应的最靠左的左端点，满足区间中最大值与最小值的差不超过 limit。
注意到随着右端点向右移动，左端点也将向右移动，于是使用滑动窗口解决本题。利用红黑树（treemap）的特点来比较快地找到窗口中的最大值和最小值
时间复杂度：O(nlogn)，其中 n 是数组长度。向有序集合中添加或删除元素都是 O(logn) 的时间复杂度。每个元素最多被添加与删除一次。
空间复杂度：O(n)，其中 n 是数组长度。最坏情况下有序集合将和原数组等大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int longestSubarray(int[] nums, int limit) {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int len = nums.length;
int left = 0, right = 0;
int result = 0;
while (right < len) {
map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
while (map.lastKey() - map.firstKey() > limit) {
map.put(nums[left], map.get(nums[left]) - 1);
if (map.get(nums[left]) == 0) {
map.remove(nums[left]);
}
left++;
}
result = Math.max(result, right - left + 1);
right++;
}
return result;
}
}
在方法一中，我们仅需要统计当前窗口内的最大值与最小值，因此我们也可以分别使用两个单调队列解决本题。
在实际代码中，使用一个单调递增的队列 queMin 维护最小值，一个单调递减的队列 queMax 维护最大值。这样只需要计算两个队列的队首的差值，即可知道当前窗口是否满足条件。
时间复杂度：O(n)，其中 n 是数组长度。最多遍历该数组两次，两个单调队列入队出队次数也均为 O(n)。
空间复杂度：O(n)，其中 n 是数组长度。最坏情况下单调队列将和原数组等大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int longestSubarray(int[] nums, int limit) {
Deque<Integer> queMax = new LinkedList<Integer>();
Deque<Integer> queMin = new LinkedList<Integer>();
int len = nums.length;
int left = 0, right = 0;
int result = 0;
while (right < len) {
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++;
}
result = Math.max(result, right - left + 1);
right++;
}
return result;
}
}