Sliding Window Maximum II(with double ended queue)

Idea: 1. Store the window data in a double ended queue.

Observations: a. If new entered data element is bigger than some stored data elements in the queue, the smaller data can be ignored.

b. Using double linked list queue, we could maintain a structure with both time and value sorted.

2. De-Queue the back for the data that is smaller than the current value.

3. De-Queue the front for the data that is out of data.

C++:
01 typedef pair <int, int> Pair;
02 void maxWindowSlide(int A[], int n, int w, int B[])
03 {
04     deque <Pair> Q;
05     for(int i=0;i<w;i++){
06         while((!Q.empty())&&(A[i]>Q.back().first))
07             Q.pop_back();
08         Q.push_back(Pair(A[i],i));
09     }
10     for(int i=w;i<n;i++){
11         Pair p=Q.front();
12         B[iw]=p.first;
13         while((!Q.empty())&&(A[i]>Q.back().first)){
14             Q.pop_back();
15         }
16         while((!Q.empty())&&(Q.front().second<=iw)){
17             Q.pop_front();
18         }
19         Q.push_back(Pair(A[i],i));
20     }
21     B[nw]=Q.front().first;
22 }
Advertisements
This entry was posted in Stack and Queue. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s