3. Sliding Window maximum code example

Example: sliding window maximum

int[] slidingWindowMaximum(int arr[], int n, int k)
{
   q = Dequeue()   
   ans = []
   // for First K elements
   for( i = 0 to k-1)
   {
       while(!q.empty() and  arr[i] >= arr[q.back()])
       {
           // Remove the indices of elements that are smaller than the current elements
           q.pop_back()
       }    
       q.push_back(i)
   }
   // the element at the front has index of the highest element in the window
   ans.append(arr[q.front()])
   // for rest elements
   for(i = k to n-1)
   {
        // drop the elements that are out of window
        while(!q.empty() and q.front() <= i-k)
            q.pop_front()
        
        // remove those elements smaller than the current element from back
        while(!q.empty() and arr[i] >= arr[q.back()])
            q.pop_back()    
        q.push_back(i)
        ans.append(arr[q.front()])
   }   
   return ans
}

Tags:

Misc Example