239. Sliding Window Maximum

Posted on | Edited on | Views: 1

LeetCode

Approach 1: Use a hammer

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
class 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: Deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class 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;
    }
}


0%