Sliding Window

Question 1

(Hard) Sliding Window Maximum

Given array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window.

Return the max in every sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3

Output: [3,3,5,5,6,7]

Explanation:

WindowPosition Max

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

Answer 1

Approach:

Standard Use case of a deque.

1. for every sliding window position remove the elements from deque from last which are out of the window.
2. And for every new number remove from first all the numbers in deque smaller than this new number. Since these no.s are irrelevant.

And finally, insert the new number.

public int[] maxSlidingWindow(int[] nums, int k) {

 Deque\< Integer\> deque = new LinkedList();
 int[] res = new int[nums.length-k+1];
 deque.add(0);
 int pos=0;

for(int i=1;i< k;i++){
if(nums[i] > nums[deque.peekLast()]){
while( deque.size() > 0 && nums[deque.peekLast()] < nums[i]) deque.pollLast();
deque.add(i);
}
else deque.add(i);
}
res[pos++]=nums[deque.peekFirst()];

for( int i=k; i < nums.length; i++){
//Discard elements out of the window
while(deque.size() > 0 && deque.peekFirst() < i-k+1) deque.pollFirst();
//Discard elements less than the incoming element
while(deque.size() > 0 && nums[deque.peekLast()] < nums[i]) deque.pollLast();
deque.add(i);
res[pos++]=nums[deque.peekFirst()];
}
return res;
}