题目输出一个n，一个k，分别代表n个数，长度为k的框，求狂每移动一次，框里面的最大值最小值
样例
8 3 1 3 -1 -3 5 3 6 7 1 3 -1 3 -1 -3 -1 -3 5 -3 5 3 5 3 6 3 6 7最小
-1 -3 -3 -3 3 3最大
3 3 5 5 6 7暴力复杂度高，这里用单调队列最小值 （单调递增的队列）1 这个队列可以可以尾巴和头都去数。2 当尾巴的数大于要存进来的数时候，尾巴弹出3 当队列头的数和尾巴的数之间的距离大于等于k，头的数弹出(这题cin cout可能会超时） 每次队列中的数字是这样变化的 11 3 //3大于1，存入-1 //-1小于3，3弹出。 -1小于1，1弹出-3-3 5-3 33 6 //-3 与 6 的距离大于k-1，-3弹出3 6 7输出 队列头 就行
最大值 是单调递增区别不大 #include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; struct node //模拟的队列，place记录下标，nub记录数 { int place,nub; }que[1100000]; int v[1100000]; int n,k; void findmin() { memset(que,0,sizeof(que)); int head=1,tail=0; for(int i=1;i<=k-1;++i) // 先把前k-1个数预处理进去队列中 { while(que[tail].nub>=v[i] && tail>=head) { tail--; } tail++; que[tail].nub=v[i]; que[tail].place=i; } for(int i=k;i<=n;++i) { while(que[tail].nub>=v[i] && tail>=head) { tail--; } tail++; que[tail].nub=v[i]; que[tail].place=i; while(que[tail].place-que[head].place>=k) { head++; } printf("%d ",que[head].nub); } } void findmax() { memset(que,0,sizeof(que)); int head=1,tail=0; for(int i=1;i<=k-1;++i) { while(que[tail].nub<=v[i] && tail>=head) { tail--; } tail++; que[tail].nub=v[i]; que[tail].place=i; } for(int i=k;i<=n;++i) { while(que[tail].nub<=v[i] && tail>=head) { tail--; } tail++; que[tail].nub=v[i]; que[tail].place=i; while(que[tail].place-que[head].place>=k) { head++; } printf("%d ",que[head].nub); } } int main() { cin>>n>>k; FOR(i,1,n) { cin>>v[i]; } findmin(); printf("\n"); findmax(); }
转载于:https://www.cnblogs.com/jrfr/p/11250699.html
