Sliding Window Maximum
/***
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. Following is an example:
The
array is [1 3 -1 -3 5 3 6 7], and w is 3.
Window
position 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
Input:
A long array A[], and a window width w
Output:
An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement:
Find a good optimal way to get B[i]
Solution:
1)
Brute force: O(kn)
2)
heap O(nlogk)
3)
deque: O(n)
Details(3):
Tricks:
when meet the new member "new", check the back of deque Q, if new
> Q.back(), pop_back() until new<= Q.back().
In
this way, Q.front() is the maximum
Note
that if the last first member in sliding window equals Q.front(), do
Q.pop_front(),
then
check the new sliding member in sliding window using above tricks.
In
this way, each member in array only can be push, pop at most only once, thus
the complexity is O(n)
***/
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
vector<int> getMax_slidingWindow(int *in, int sz, int w) {
vector<int> maxW;
deque<int> slidingQ;
for(int i=0; i<w; i++) {
while(!slidingQ.empty() && in[i] > slidingQ.back())
slidingQ.pop_back();
slidingQ.push_back(in[i]);
}
maxW.push_back(slidingQ.front());
for(int i=1; i<sz-w+1; i++) {
if(in[i-1] == slidingQ.front())
slidingQ.pop_front();
while(!slidingQ.empty() && in[i+w-1] > slidingQ.back())
slidingQ.pop_back();
slidingQ.push_back(in[i+w-1]);
maxW.push_back(slidingQ.front());
}
return maxW;
}
void main() {
int a[] = {2, 3, 4, 2, 6, 2, 5, 1};
int sz = sizeof(a) / sizeof(int);
int w = 3;
vector<int> maxW = getMax_slidingWindow(a, sz, w);
for(int i=0; i<maxW.size(); i++)
cout<<maxW[i]<<" ";
cout<<endl;
}
Comments
Post a Comment