You are given an array of integers arr, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Method 1:- Use of Priority Queue(O(nlogn)
int n = arr.size();
vector<int> ans;
priority_queue<pair<int,int>> pq;
for(int i=0;i<k;i++){
pq.push({arr[i],i});
}
ans.push_back(pq.top().first);
for(int i=k;i<n;i++){
pq.push({arr[i],i});
while(pq.top().second<=i-k){
pq.pop();
}
ans.push_back(pq.top().first);
}
return ans;
Method 2:- Use of Maximum Queue:- In this method we mantain a queue which can tell us the maximum value of the particular Sliding Window
int n = arr.size();
vector<int> ans;
//Implementation of Maximum Queue
deque<int> q;
auto add = [&](int x){
while(!q.empty() && q.back()<x){ //q.back()>x(To convert to Minimum Queue)
q.pop_back();
}
q.push_back(x);
};
auto remove = [&](int x){
if(q.front()==x){
q.pop_front();
}
};
auto update = [&](){
ans.push_back(q.front());
};
//End of Implementation of Maximum Queue
for(int i=0;i<n;i++){
int j=i-k;
add(arr[i]);
if(j>=0){
remove(arr[j]);
}
if(i>=k-1){
update();
}
}
return ans;
Here in Implementation I used Lamda Functions If you dont know you can use normal functins instead it works the same.
You can read about this technique in detail from CP Algorithms :- Minimum Queue The implementation there is for a minimum queue this is for a maximum queue