Sliding window on A

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Produce an array  B[], B[i] is the maximum value of from A[i] to A[i+w-1]

Solution 


- a naive solution is O(n w)
- an heap based solution could be O( n lg w), but we need to change the heap for maintaining n-w max positions and invalidate when the windows move. too complicated and not sure we can make it


- we can maintain a queue or better a dequeue while processing the array. The size of the queue Q is w and the key observation is that when we see an element A[j] we can remove each element in Q such that A[j] > Q[z] because we are looking for the max and those elements are not max given the esistence of A[j]. In doing so, we keep the current maximum at front and we remove the other elements from the back of the deque. Each element will enter 1 time in the queue and will exit at most 1 time, so the total complexity is O(n) which is pretty good. For keeping the sliding window we push current Array index so we need to remove from front when out of current window

1. #include  
2.   
3. void maxSlidingWindow(int A[], int n, int w, int B[])  
4. {  
5.    deque<int> Q;  
6.     
7.    //Initilize deque Q for first window  
8.    for (int i = 0; i < w; i++)  
9.    {  
10.        while (!Q.empty() && A[i] >= A[Q.back()])  
11.            Q.pop_back();  
12.        Q.push_back(i);  
13.    }  
14.     
15.    for (int i = w; i < n; i++)  
16.    {  
17.        B[i-w] = A[Q.front()];  
18.   
19.        //update Q for new window  
20.        while (!Q.empty() && A[i] >= A[Q.back()])  
21.            Q.pop_back();  
22.   
23.        //Pop older element outside window from Q      
24.        while (!Q.empty() && Q.front() <= i-w)  
25.            Q.pop_front();  
26.         
27.        //Insert current element in Q  
28.        Q.push_back(i);  
29.    }  
30.    B[n-w] = A[Q.front()];  
31. }