首页 > 代码库 > POJ2823
POJ2823
题目:给出n个数(n<=1000000)和k,从左到右依次求每k个数字的最大,最小值
红果果的单调队列,算是一道学习单调队列的好题了。
单调队列,名字听起来挺高大上,其实很简单。
同样用到一个普通的队列,一个头指针和一个尾指针,队列用结构体定义,包含两个成员,该元素的值和改元素在原数组中的下标。
单调队列,顾名思义,就是说这个队列里的元素是单调的,递增或递减。查询最小值是O(1),总的复杂度是O(N)这里以单调递增为例,可以求出每个k区间内的最小值。单调队列里面元素是递增的,对于每一个新入队的元素,先从队尾开始向前找第一个小于这个要入队的元素,然后把找到的这个元素后面的所有队员全部从队尾出队(将尾指针移到所找到的元素的后面一个即可),这样这个元素就入队了。对于每个区间,队头元素就是该区间的最小值。
举个单调队列的例子。
8
1 3 -1 -3 5 3 6 7
一开始,队列为空,
1 入队
3 入队,从队尾找第一个小于3的元素,即 1 ,接着将 3放到1后
-1 入队 1、3都大于 -1 所以1和3 都出队,-1 则排到了队头
-3 入队 -3 小于 -1,-1出队,-3为队头元素
5 入队,5大于-3 5排到-3后
3 入队 5出队,3排到-3后,这时队列只有两个元素 -3 和3
6 入队,3小于6 则6排到队尾3的后面
7 入队 排到队尾
其实这个东西很简单,具体看看程序想一想就理解。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int maxn = 1000005; 6 struct node 7 { 8 int value; 9 int index;10 }que[maxn];11 int a[maxn];12 int front,rear;13 int main()14 {15 //freopen("in.txt","r",stdin);16 int n,k;17 while(cin>>n>>k)18 {19 for(int i = 1;i<=n;++i)scanf("%d",a+i);20 front = 1;rear = 0;21 //求最小值22 for(int i = 1;i<k;++i)23 {24 //在队列非空,情况下,从队尾找小于a[i]的第一个位置25 while(front<=rear && que[rear].value>=a[i])rear--;26 que[++rear].value =http://www.mamicode.com/ a[i];27 que[rear].index = i;28 }29 for(int i = k;i<=n;++i)30 { //删除队尾不需要的元素,将第k个元素入队31 while(front<=rear && que[rear].value>=a[i])rear--;32 que[++rear].value =http://www.mamicode.com/ a[i];33 que[rear].index = i;34 //维护队列的长度不超过k35 if(que[front].index<=i-k)front++;36 printf("%d ",que[front].value);37 }38 printf("\n");39 //求最大值40 front = 1;rear = 0;41 for(int i = 1;i<k;++i)42 {43 while(front<=rear && que[rear].value<=a[i])rear--;44 que[++rear].value =http://www.mamicode.com/ a[i];45 que[rear].index = i;46 }47 for(int i = k;i<=n;++i)48 {49 while(front<=rear && que[rear].value<=a[i])rear--;50 que[++rear].value =http://www.mamicode.com/ a[i];51 que[rear].index = i;52 if(que[front].index<=i-k)front++;53 printf("%d ",que[front].value);54 }55 56 }57 return 0;58 }
POJ2823
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。