题目分析
如果一个子数组达标，也就是它内部的最大值减去最小值小于等于给定限制limit， 则其内部任意小范围一定也达标，因为范围变小，最大值只可能变小或者不变，而最小值只可能变大或者不变。
如果一个子数组不达标，则再扩大范围一定会更加不达标，因为范围变大，最大值只可能上升或者不变，而最小值只可能下降或者不变。
先固定左边界l，右边界r不断右移扩展窗口，每次判断新加入的数是否使窗口达标，如果达标，则继续拓展，不达标则停止，计算以当前l开头的达标子数组的最大长度。
求解代码
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
public static int MAXN = 100001;
public static int[] maxDeque = new int[MAXN];
public static int[] minDeque = new int[MAXN];
public static int maxh,maxt,minh,mint;
public static int[] arr;
public static int longestSubarray(int[] nums,int limit){
maxh = maxt = minh = mint = 0;
arr = nums;
int n = arr.length;
int ans = 0;
for(int l=0,r=0;l<n;l++){
while(r<n&&ok(limit,nums[r])){
push(r++);
}
ans = Math.max(ans, r-l);
pop(l);
}
return ans;
}
public static boolean ok(int limit,int number){
int max = maxh <maxt?Math.max(arr[maxDeque[maxh]], number):number;
int min = minh <mint?Math.min(arr[minDeque[minh]], number):number;
return max-min<=limit;
}
public static void push(int r){
while (maxh<maxt&&arr[maxDeque[maxt-1]]<=arr[r]) {
maxt--;
}
maxDeque[maxt++]=r;
while (minh<mint&&arr[minDeque[mint-1]]>=arr[r]) {
mint--;
}
minDeque[mint++]=r;
}
public static void pop(int l) {
if (maxh < maxt && maxDeque[maxh] == l) {
maxh++;
}
if (minh < mint && minDeque[minh] == l) {
minh++;
}
}
|