classSolution { public: //Function to find maximum of each subarray of size k. vector <int> max_of_subarrays(int *arr, int n, int k) { if(n < k) return {}; vector<int> res; priority_queue<int> window, remove; for(int i = 0; i <= k - 1; i++) window.push(arr[i]); res.push_back(window.top()); for(int i = k; i < n; i++) { remove.push(arr[i-k]); window.push(arr[i]); while(!remove.empty() and remove.top() == window.top()) { window.pop(); remove.pop(); } res.push_back(window.top()); } return res; } };
classSolution { public: //Function to find maximum of each subarray of size k. vector <int> max_of_subarrays(int *arr, int n, int k) { if(n < k) return {}; vector<int> res; deque<int> dq; for(int i = 0; i <= k - 1; i++) { while(!dq.empty() and arr[dq.back()] <= arr[i]) dq.pop_back(); dq.push_back(i); } res.push_back(arr[dq.front()]); for(int i = k; i < n; i++) { while(!dq.empty() and dq.front() <= i - k) dq.pop_front(); while(!dq.empty() and arr[dq.back()] <= arr[i]) dq.pop_back(); dq.push_back(i); res.push_back(arr[dq.front()]); } return res; } };