求解代码
准备一个数组作为双端队列deque，用h（head）和t（tail）表示队列的头和尾位置。
双端队列要维持从左往右大到小的顺序。
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
|
public static int MAXN = 100001;
public static int[] deque = new int[MAXN];
public static int h,t;
public static int[] maxSlidingWindow(int[] arr,int k){
h = t = 0;
int n = arr.length;
for(int i=0;i<k-1;i++){
while(h<t&&arr[deque[t-1]]<=arr[i]){
t--;
}
deque[t++]=i;
}
int m = n-k+1;
int[] ans = new int[m];
for(int l=0,r=k-1;l<m;l++,r++){
while(h<t&&arr[deque[t-1]]<=arr[r]){
t--;
}
deque[t++]=r;
ans[l]=arr[deque[h]];
if(deque[h]==l){
h++;
}
}
return ans;
}
|