单调队列求第k大值

//单调队列求第k大值
#include 
#include using namespace std;#define MAX 1000001
int A[MAX]; //存储数据
int Q[MAX]; //队列
int P[MAX]; //存储A[i]中的下标i
int Min[MAX];  //输出最小
int Max[MAX];  //输出最大
int n,k;void get_min()
{int i;int head=1,tail=0;for(i=0; i1; i++)  //先把前两个入队{while(head<=tail && Q[tail]>=A[i])  //队尾元素大于要插入的数--tail;Q[++tail]=A[i];P[tail]=i;}for(; iwhile(head<=tail && Q[tail]>=A[i])--tail;Q[++tail]=A[i];P[tail]=i;while(P[head]1)  //判断数是否过时，即窗口是否已经划过这个数，我这是从0开始计数的。{head++;}Min[i-k+1]=Q[head];}
}void get_max()
{int i;int head=1,tail=0;for(i=0; i1; i++){while(head<=tail && Q[tail]<=A[i])   //队尾元素小于要插入的值--tail;Q[++tail]=A[i];P[tail]=i;}for(; iwhile(head<=tail && Q[tail]<=A[i])   //队尾元素小于要插入的值--tail;Q[++tail]=A[i];P[tail]=i;while(P[head]1){head++;}Max[i-k+1]=Q[head];}
}void output()
{int i;      //输出最下值 for(i=0; i1; i++){if(i==0)printf("%d",Min[i]);elseprintf(" %d",Min[i]);}printf("\n");//输出最大值for(i=0; i1; i++){if(i==0)printf("%d",Max[i]);elseprintf(" %d",Max[i]);}printf("\n");
}int main()
{int i;freopen("acm.txt","r",stdin);scanf("%d%d",&n,&k);for(i=0; iscanf("%d",&A[i]);}get_min();get_max();output();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！