Maximum Queue(Sliding Window Maximum)

Revision en1, by dakshdixit183, 2023-09-18 11:09:19

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.

Problem Link

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

Tags 2 pointers, data structures, leetcode, cp-algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dakshdixit183 2023-09-18 11:09:19 2202 Initial revision (published)