Advertisement
akashtadwai

max of all subarrays of size k

Jul 19th, 2021
1,899
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. class Solution
  2. {
  3.   public:
  4.   deque<pair<int,int> > dq;
  5.   int cnt_added=0,cnt_removed=0;
  6.   void add(int ele){
  7.       while(!dq.empty() and dq.back().first<ele) dq.pop_back();
  8.       dq.push_back({ele,cnt_added});
  9.       cnt_added++;
  10.   }
  11.   void del(){
  12.       if(!dq.empty() and dq.front().second==cnt_removed) dq.pop_front();
  13.       cnt_removed++;
  14.   }
  15.   int mx(){
  16.       return dq.front().first;
  17.   }
  18.     //Function to find maximum of each subarray of size k.
  19.     vector <int> max_of_subarrays(int *arr, int n, int k)
  20.     {
  21.         // your code here
  22.         for(int i=0;i<k;i++) add(arr[i]);
  23.         vector<int>ans;
  24.         ans.push_back(mx());
  25.        
  26.         for(int i=k;i<n;i++){
  27.             del();
  28.             add(arr[i]);
  29.             ans.push_back(mx());
  30.         }
  31.         return ans;
  32.     }
  33. };
  34.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement