简单说下题目：N个数，大小为k的窗口，求每个窗口的最大值和最小值 input n个数，窗口为k, (n<=1e6) output 每个窗口的最大最小值
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int M[N],m[N];//存最大值和最小值 struct Node { int p,q;//p:数字,q:数字下标 }data; deque<Node>vis1,vis2;//定义两个Node型的单调队列 int t1,t2; int main() { ios::sync_with_stdio(false); int n,k,x,head1,head2;//head记录队列第一个数的下标 cin>>n>>k; for(int i=1;i<=n;i++) { cin>>x; data.p=x;data.q=i;//记录数字及其下标 //求最小值 while(!vis1.empty()&&x<=vis1.back().p) vis1.pop_back(); vis1.push_back(data);//注意队列为Node型 head1=vis1.front().q; if(i-head1>=k) vis1.pop_front();//如果队列中的数超过k个，出队 if(i>=k)//一个窗口有k个数时 m[++t1]=vis1.front().p; //求最大值 while(!vis2.empty()&&x>=vis2.back().p) vis2.pop_back(); vis2.push_back(data); head2=vis2.front().q; if(i-head2>=k) vis2.pop_front(); if(i>=k) M[++t2]=vis2.front().p; } for(int i=1;i<t1;i++) cout<<m[i]<<" "; cout<<m[t1]<<endl; for(int i=1;i<t2;i++) cout<<M[i]<<" "; cout<<M[t2]<<endl; return 0; }input 8 3 1 3 -1 -3 5 3 6 7 output -1 -3 -3 -3 3 3 3 3 5 5 6 7
