raghuvanshraj

239.cpp

Jul 26th, 2021
608
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  20.04.2020 08:55:15 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. void insert_elt(deque<int> &deq, vector<int> &arr, int i) {
  10.     while (not deq.empty() and arr[deq.back()] <= arr[i]) {
  11.         deq.pop_back();
  12.     }
  13.  
  14.     deq.push_back(i);
  15. }
  16.  
  17. void delete_idx(deque<int> &deq, int i) {
  18.     while (not deq.empty() and deq.front() <= i) {
  19.         deq.pop_front();
  20.     }
  21. }
  22.  
  23. vector<int> maxSlidingWindow(vector<int> &arr, int k) {
  24.     int n = arr.size();
  25.     deque<int> deq;
  26.     for (int i = 0; i <= k - 2; ++i) {
  27.         insert_elt(deq, arr, i);
  28.     }
  29.  
  30.     vector<int> ans;
  31.     for (int i = k - 1, j = 0; i <= n - 1; ++i, ++j) {
  32.         insert_elt(deq, arr, i);
  33.         ans.push_back(arr[deq.front()]);
  34.         delete_idx(deq, j);
  35.     }
  36.  
  37.     return ans;
  38. }
  39.  
  40. int main(int argc, char const *argv[]) {
  41.     int n;
  42.     cin >> n;
  43.     vector<int> arr(n);
  44.     for (int i = 0; i <= n - 1; ++i) {
  45.         cin >> arr[i];
  46.     }
  47.     int k;
  48.     cin >> k;
  49.  
  50.     vector<int> ans = maxSlidingWindow(arr, k);
  51.     for (int x : ans) {
  52.         cout << x << ' ';
  53.     }
  54.  
  55.     return 0;
  56. }
RAW Paste Data