akashtadwai

queue

Jul 24th, 2021
1,001
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  vector <int> max_of_subarrays(int *arr, int n, int k)
  2.     {
  3.         // your code here
  4.         for(int i=0;i<k;i++) add(arr[i]);
  5.         vector<int>ans;
  6.         ans.push_back(mx());
  7.        
  8.         for(int i=k;i<n;i++){
  9.             del(arr[i-k]);
  10.             add(arr[i]);
  11.             ans.push_back(mx());
  12.         }
  13.         return ans;
  14.     }
  15. private:
  16.     deque<int>dq;
  17.   void add(int ele){
  18.       while(!dq.empty() and dq.back()<ele) dq.pop_back();
  19.       dq.push_back(ele);
  20.   }
  21.   void del(int ele){
  22.       if(!dq.empty() and dq.front()==ele) dq.pop_front();
  23.   }
  24.   int mx(){
  25.       return dq.front();
  26.   }
RAW Paste Data