The problem link may be found here.
Explanation:
- Use Deque to keep track of elements of the variety of candies.
- If i is greater that allowed variety of Candies pop the front element of the queue
- Based of condition only keep the maximum element, pop everything thats smaller than the ith element
1 #include<bits/stdc++.h>
2 using
namespace std;
3 void sliding(vector<int>&v,int k){
4 deque<int>q;
5 vector<int>res;
6 for(int i=0;i<v.size();i++){
7 while(!q.empty() && i-q.front()>=k){
8
q.pop_front();
9 }
10 while(!q.empty() && v[q.back()]< v[i]){
11 q.pop_back();
12 }
13 q.push_back(i);
14 if(i>=k-1)res.push_back(v[q.front()]);
15 }
16 for(int i=0;i<res.size();i++){
17 cout<<res[i]<<" ";
18 }
19 }
20 int main(){
21 int t,n,k,m;
22
23 scanf("%d",&t);
24 while(t--){
25 cin>>n>>k;
26 vector<int>v;
27 vector<int>ans;
28 for(int i=0;i<n;i++){
29 cin>>m;
30 v.push_back(m);
31 }
32 sliding(v,k);
33
34 cout<<endl;
35 }
36
37
38 return 0;}
