(73). 25.1. Deque (Sliding Windows Maximum Using Deque) - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

//Deque code

#include <bits/stdc++.h> using namespace std;

int main(){ deque dq; dq.push_back(1); //print 1 on bottom dq.push_back(2); //print 1 on bottom dq.push_front(3); //print 3 on top dq.push_front(4); //print 4 on top cout << "push operation: "; for(auto i : dq){ cout << i << " "; } cout << endl;

cout << "Pop operation: ";
dq.pop_back(); //delete 4
dq.pop_front(); //delete 2
for(auto i : dq){
	cout << i << " ";
}
cout << endl;

cout << "Size: " << dq.size();
return 0;

}

/* OUTPUT: push operation: 4 3 1 2 Pop operation: 3 1 Size: 2 */

//SLIDING WINDOWS MAXIMUM

#include <bits/stdc++.h> using namespace std;

int main(){ int n,k; cin >> n >> k;

vector<int> a(n);
for(auto &i: a){
	cin >> i;
}

deque<int> q;
vector<int> ans;
for(int i=0; i<k; i++){
    while(!q.empty() && a[q.back()] < a[i]){
        q.pop_back();
    }
    q.push_back(i);
}
ans.push_back(a[q.front()]);
for(int i=k; i<n; i++){
    if(q.front() == i-k){
        q.pop_front();
    }
    while(!q.empty() && a[q.back()] < a[i]){
        q.pop_back();
    }
    q.push_back(i);
    ans.push_back(a[q.front()]);
}

for(auto i : ans){
    cout << i << " ";
}

return 0;

}

/* OUTPUT: Input: 6 2 3 4 9 1 -4 10 4 9 9 1 10 */

⚠️ **GitHub.com Fallback** ⚠️