Approach 1: Use a hammer1
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
34class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + k; j++)
max = Math.max(max, nums[j]);
output[i] = max;
}
return output;
}
}
/* O((N-k+1)*klogk)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len=nums.length;
if(len<=k){
Arrays.sort(nums);
return new int[]{nums[len-1]};
}
int lenk=len-k+1;
int[] res=new int[lenk];
int i=0;
while(i+k<=len){
int[] tmp=nums.clone();
Arrays.sort(tmp,i,i+k);
res[i]=tmp[i+k-1];
i++;
}
return res;
}
}*/
link
Approach 2: Deque1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n=nums.length;
int[] res=new int[n-k+1];
LinkedList<Integer> dq=new LinkedList<>();
for(int i=0;i<n;i++){
if(!dq.isEmpty()&&dq.peek()<i-k+1) dq.removeFirst();//Keep only the indexes of elements from the current sliding window.
while(!dq.isEmpty()&&nums[i]>nums[dq.peekLast()]) dq.removeLast();//Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.
dq.addLast(i);
if(i-k+1>=0) res[i-k+1]=nums[dq.peekFirst()];
}
return res;
}
}
