Ronzii's Blog

Just your average geek's blog

Sliding Window Maximum

#include <iostream>
#include <queue>
using namespace std;
void printArray(int A[],int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
void maxSlidingWindow(int A[], int n, int w, int B[])
{
    deque<int> q;
    int i=0;
    for(i=0; i<w; i++)
    {
        while(!q.empty() && A[i]>=A[q.back()])
        {
            q.pop_back();
        }
        q.push_back(i);
    }
    for(i=w; i<n; i++)
    {
        B[i-w] = A[q.front()];
        while(!q.empty() && A[i]>=A[q.back()])
        {
            q.pop_back();
        }
        while(!q.empty() && q.front()<=i-w)
        {
            q.pop_front();
        }
        q.push_back(i);
    }

    B[i-w] = A[q.front()];
    printArray(B,n-w+1);
}
int main()
{
    int A[] = {17,10,13,18,19,20,-3,15,11,6,7,1,2,3};
    int n = sizeof(A)/sizeof(int);
    int w =5;
    int B[n];
    maxSlidingWindow(A,n,w,B);
    return 0;

}

March 1, 2012 Posted by | C++ | , , , | Leave a comment