单调队列
spoiler posted @ 2011年4月09日 17:10 in 未分类 , 2027 阅读
一直弄不明白单调队列是什么，在网上也找不到易懂的介绍。最后结合别人博客上的介绍和程序看才理解是怎么回事。
我们从最简单的问题开始：
给定一个长度为N的整数数列a(i),i=0,1,...,N-1和窗长度k.
要求：
f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1
问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。
解法一：
很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。
这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。
那么有没有更快一点的算法呢？
解法二：
我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。
单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。
1.首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。
2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于 i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首 元素删除。
从上面的介绍当中，我们知道，单调队列与队列唯一的不同就在于它不仅要保存元素的值，而且要保存元素的索引（当然在实际应用中我们可以只需要保存索引，而通过索引间接找到当前索引的值）。
为了让读者更明白一点，我举个简单的例子。
假设数列为：8，7，12，5，16，9，17，2，4，6.N=10,k=3.
那么我们构造一个长度为3的单调递减队列：
首先，那8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下：
0：插入8，队列为：（8，0）
1：插入7，队列为：（8，0），（7，1）
2：插入12，队列为：（12，2）
3：插入5，队列为：（12，2），（5，3）
4：插入16，队列为：（16，4）
5：插入9，队列为：（16，4），（9，5）
。。。。依此类推
那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，。。。
一直弄不明白单调队列是什么，在网上也找不到易懂的介绍。最后结合别人博客上的介绍和程序看才理解是怎么回事。
我们从最简单的问题开始：
给定一个长度为N的整数数列a(i),i=0,1,...,N-1和窗长度k.
要求：
f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1
问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。
解法一：
很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。
这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。
那么有没有更快一点的算法呢？
解法二：
我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。
单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。
1.首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。
2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于 i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首 元素删除。
从上面的介绍当中，我们知道，单调队列与队列唯一的不同就在于它不仅要保存元素的值，而且要保存元素的索引（当然在实际应用中我们可以只需要保存索引，而通过索引间接找到当前索引的值）。
为了让读者更明白一点，我举个简单的例子。
假设数列为：8，7，12，5，16，9，17，2，4，6.N=10,k=3.
那么我们构造一个长度为3的单调递减队列：
首先，那8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下：
0：插入8，队列为：（8，0）
1：插入7，队列为：（8，0），（7，1）
2：插入12，队列为：（12，2）
3：插入5，队列为：（12，2），（5，3）
4：插入16，队列为：（16，4）
5：插入9，队列为：（16，4），（9，5）
。。。。依此类推
那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，。。。
一、 什么是单调（双端）队列
单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。
单调队列，又名双端队列。双端队列，就是说它不同于一般的队列只能在队首删除、队尾插入，它能够在队首、队尾同时进行删除。
【单调队列的性质】
一般，在动态规划的过程中，单调队列中每个元素一般存储的是两个值：
1、在原数列中的位置（下标）
2、 他在动态规划中的状态值
而单调队列则保证这两个值同时单调。
从以上看，单调队列的元素最好用一个类来放，不这样的话，就要开两个数组。。。
单调队列：单调队列 即保持队列中的元素单调递增（或递减）的这样一个队列，可以从两头删除，只能从队尾插入。单调队列的具体作用在于，由于保持队列中的元素满足单调性，对手元素便是极小值（极大值）了。
http://poj.org/problem?id=2823
- //poj-2823--单调队列
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int MAX = 1000001;
- //两个单调队列
- int dq1[MAX]; //一个存单调递增
- int dq2[MAX]; //一个存单调递减
- int a[MAX];
- inline bool scan_d(int &num) // 这个就是 加速的 关键了
- {
- char in;bool IsN=false;
- in=getchar();
- if(in==EOF)
- return false;
- while(in!='-'&&(in<'0'||in>'9')) in=getchar();
- if(in=='-') { IsN=true;num=0;}
- else num=in-'0';
- while(in=getchar(),in>='0'&&in<='9')
- {
- num*=10,num+=in-'0';
- }
- if(IsN)
- num=-num;
- return true;
- }
- int main(void)
- {
- int i,n,k,front1,front2,tail1,tail2,start,ans;
- while(scanf("%d %d",&n,&k)!=EOF)
- {
- for(i = 0 ; i < n ; ++i)
- scan_d(a[i]);
- front1 = 0, tail1 = -1;
- front2 = 0, tail2 = -1;
- ans = start = 0;
- for(i = 0 ; i < k ; ++i)
- {
- while(front1 <= tail1 && a[ dq1[tail1] ] <= a[i]) //当前元素大于单调递增队列的队尾元素的时候，队尾的元素依次弹出队列，直到队尾元素大于当前当前元素的时候，将当前元素插入队尾
- --tail1;
- dq1[ ++tail1 ] = i; //只需要记录下标即可
- while(front2 <= tail2 && a[ dq2[tail2] ] >= a[i]) //当前元素小于单调递减队列的队尾元素的时候，队尾的元素依次弹出队列，直到队尾元素小于当前当前元素的时候，将当前元素插入队尾
- --tail2;
- dq2[ ++tail2 ] = i; //只需要记录下标即可
- }
- printf("%d ",a[ dq2[ front2 ] ]);
- for( ; i < n ; ++i)
- {
- while(front2 <= tail2 && a[ dq2[tail2] ] >= a[i])
- --tail2;
- dq2[ ++tail2 ] = i;
- while(dq2[ front2 ] <= i - k)
- ++front2;
- if(i != n-1)
- printf("%d ",a[ dq2[ front2 ] ]);
- }
- printf("%d\n",a[ dq2[ front2 ] ]);
- //输出最大值
- printf("%d ",a[ dq1[ front1 ] ]);
- for(i=k ; i < n ; ++i)
- {
- while(front1 <= tail1 && a[ dq1[tail1] ] <= a[i])
- --tail1;
- dq1[ ++tail1 ] = i;
- while(dq1[ front1 ] <= i - k)
- ++front1;
- if(i != n-1)
- printf("%d ",a[ dq1[ front1 ] ]);
- }
- printf("%d\n",a[ dq1[ front1 ] ]);
- }
- return 0;
- }
http://acm.hdu.edu.cn/showproblem.php?pid=3530 Subsequence
- /*
- 题意：给出一个序列，求最长的连续子序列，使得 M<=Max-Min<=K
- n <= 10^5
- 依次枚举剩下的N-1个元素，并且将当前未入队的第一个元素和队尾元素比较，当且仅当队列为非空并且队尾元素的值小于当前未入队的元素时，
- 将队尾元素删除(也就是队尾指针-1），因为当前的元素比队尾元素大，所以在区间内队尾元素不会是最大值了。
- 重复这个过程直到队列空或者队尾元素比当前元素大，
- */
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int MAX = 100001;
- //两个单调队列
- int dq1[MAX]; //一个存单调递增
- int dq2[MAX]; //一个存单调递减
- int a[MAX];
- inline bool scan_d(int &num) // 这个就是 加速的 关键了
- {
- char in;bool IsN=false;
- in=getchar();
- if(in==EOF)
- return false;
- while(in!='-'&&(in<'0'||in>'9')) in=getchar();
- if(in=='-') { IsN=true;num=0;}
- else num=in-'0';
- while(in=getchar(),in>='0'&&in<='9')
- {
- num*=10,num+=in-'0';
- }
- if(IsN)
- num=-num;
- return true;
- }
- int main(void)
- {
- int i,n,m,k,front1,front2,tail1,tail2,start,ans;
- while(scanf("%d %d %d",&n,&m,&k) != EOF)
- {
- for(i = 0 ; i < n ; ++i)
- scan_d(a[i]);
- front1 = 0, tail1 = -1;
- front2 = 0, tail2 = -1;
- ans = start = 0;
- for(i = 0 ; i < n ; ++i)
- {
- while(front1 <= tail1 && a[ dq1[tail1] ] <= a[i]) //当前元素大于单调递增队列的队尾元素的时候，队尾的元素依次弹出队列，直到队尾元素大于当前当前元素的时候，将当前元素插入队尾
- --tail1;
- dq1[ ++tail1 ] = i; //只需要记录下标即可
- while(front2 <= tail2 && a[ dq2[tail2] ] >= a[i]) //当前元素小于单调递减队列的队尾元素的时候，队尾的元素依次弹出队列，直到队尾元素小于当前当前元素的时候，将当前元素插入队尾
- --tail2;
- dq2[ ++tail2 ] = i; //只需要记录下标即可
- /*
- Max - Min 为两个队列的队首之差
- while(Max-Min>K) 看哪个的队首元素比较靠前，就把谁往后移动
- */
- while(a[ dq1[front1] ] - a[ dq2[front2] ] > k)
- {
- if(dq1[front1] < dq2[front2] )
- {
- start = dq1[front1] + 1;
- ++front1;
- }
- else
- {
- start = dq2[front2] + 1;
- ++front2;
- }
- }
- if(a[ dq1[front1] ] - a[ dq2[front2] ] >= m)
- {
- if(i - start +1 > ans)
- ans = i - start + 1;
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }
之所以取名为 单调队列1.是因为本来想做另外一道的，但是实在做不来……所以先铺垫一道题
看了别人的分析，很经典：
题目大意：给出一个有N个数字（-1000..1000，N<=10^5）的环状序列，让你求一个和最大的连续子序列。这个连续子序列的长度小于等于K。
分析：因为序列是环状的，所以可以在序列后面复制一段（或者复制前k个数字）。如果用s[i]来表示复制过后的序列的前i个数的和，那么任意一个子序列[i..j]的和就等于s[j]-s[i-1]。对于每一个j，用s[j]减去最小的一个s[i](i>=j-k+1)就可以得到以j为终点长度不大于k的和最大的序列了。将原问题转化为这样一个问题后，就可以用单调队列解决了。
单调队列即保持队列中的元素单调递增（或递减）的这样一个队列，可以从两头删除，只能从队尾插入。单调队列的具体作用在于，由于保持队列中的元素满足单调性，对于上述问题中的每个j，可以用O(1)的时间找到对应的s[i]。（保持队列中的元素单调增的话，队首元素便是所要的元素了）。
维护方法：对于每个j，我们插入s[j-1]（为什么不是s[j]? 队列里面维护的是区间开始的下标，j是区间结束的下标），插入时从队尾插入。为了保证队列的单调性，我们从队尾开始删除元素，直到队尾元素比当前需要插入的元素优（本题中是值比待插入元素小，位置比待插入元素靠前，不过后面这一个条件可以不考虑），就将当前元素插入到队尾。之所以可以将之前的队列尾部元素全部删除，是因为它们已经不可能成为最优的元素了，因为当前要插入的元素位置比它们靠前，值比它们小。我们要找的，是满足(i>=j-k+1)的i中最小的s[i]，位置越大越可能成为后面的j的最优s[i]。
在插入元素后，从队首开始，将不符合限制条件(i>=j-k+1)的元素全部删除，此时队列一定不为空。（因为刚刚插入了一个一定符合条件的元素）
- #include<iostream>
- #include<queue>
- using namespace std;
- #define INF 0x3fffffff
- #define N 100010*2
- int num[N],sum[N];
- int main()
- {
- int T,n,k,on;
- cin>>T;
- while(T--)
- {
- int i,j;
- cin>>n>>k;
- sum[0]=0;
- for(i=1;i<=n;i++)
- {
- scanf("%d",&num[i]);
- sum[i]=sum[i-1]+num[i];
- }
- for(i=n+1;i<n+k;i++)//continue k numbers
- sum[i]=sum[i-1]+num[i-n];
- on=n;
- n=n+k-1;
- int ans=-INF;
- int start,end;
- deque<int>q;
- q.clear();
- //枚举以j结尾的区间，找满足[j-k<=i<=j]且使sum最小的i
- for(j=1;j<=n;j++)
- {
- //delete from tail
- while(!q.empty()&&sum[j-1]<sum[q.back()])
- q.pop_back();
- while(!q.empty()&&q.front()<(j-k))//requirement:length<=k,=> i>j-k
- q.pop_front();
- q.push_back(j-1);
- if(sum[j]-sum[q.front()]>ans)
- {
- ans=sum[j]-sum[q.front()];
- start=q.front()+1;
- end=j;
- }
- }
- cout<<ans<<" "<<start<<" "<<(end>on?end%on:end)<<endl;
- }
- }
题意：给出一个n*m的矩阵，要求求出它所有r*c子矩阵里面的元素的最大值减最小值的差的最大值。
思路：二维的单调队列维护，时间复杂度为O（n^2）。
- <strong><span style="font-size:16px;">#include<iostream>
- #include<cstdio>
- #include<map>
- #include<cstring>
- #include<vector>
- #include<queue>
- #include<algorithm>
- #include<cmath>
- #include<set>
- using namespace std;
- #define N 1005
- int head,tail,mat[N][N],vmax[N][N],vmin[N][N]; //vmax[i][j]表示(i,j)到(i+d-1,j+d-1)中的最大值,vmin[i][j]表示(i,j)到(i+d-1,j+d-1)中的最小值。
- struct node
- {
- int num,id;
- };
- node que[N];
- void add_max(int num,int id)
- {
- while(head<tail&&que[tail-1].num<=num)tail--; //单调队列维护
- que[tail].id=id;
- que[tail++].num=num;
- }
- void add_min(int num,int id)
- {
- while(head<tail&&que[tail-1].num>=num)tail--;
- que[tail].id=id;
- que[tail++].num=num;
- }
- int get_num(int id)
- {
- while(head<tail&&que[head].id<id)head++;
- return que[head].num;
- }
- int main()
- {
- //freopen("a.txt","r",stdin);
- int n,m,r,c;
- while(scanf("%d%d%d%d",&n,&m,&r,&c)!=EOF)
- {
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<m;j++)
- {
- scanf("%d",&mat[i][j]);
- }
- }
- for(int i=0;i<m;i++)
- {
- head=tail=0;
- for(int j=0;j<r-1;j++)add_max(mat[j][i],j);
- for(int j=r-1;j<n;j++)
- {
- add_max(mat[j][i],j);
- vmax[j-r+1][i]=get_num(j-r+1); //这时的vmax[j-r+1][i]表示第i列中的第j-r+1行到第j行的最大值
- }
- }
- for(int i=0;i<=n-r;i++)
- {
- head=tail=0;
- for(int j=0;j<c-1;j++)add_max(vmax[i][j],j); //这里就是二维单调队列维护了
- for(int j=c-1;j<m;j++)
- {
- add_max(vmax[i][j],j);
- vmax[i][j-c+1]=get_num(j-c+1);
- }
- }
- for(int i=0;i<m;i++)
- {
- head=tail=0;
- for(int j=0;j<r-1;j++)add_min(mat[j][i],j);
- for(int j=r-1;j<n;j++)
- {
- add_min(mat[j][i],j);
- vmin[j-r+1][i]=get_num(j-r+1);
- }
- }
- for(int i=0;i<=n-r;i++)
- {
- head=tail=0;
- for(int j=0;j<c-1;j++)add_min(vmin[i][j],j);
- for(int j=c-1;j<m;j++)
- {
- add_min(vmin[i][j],j);
- vmin[i][j-c+1]=get_num(j-c+1);
- }
- }
- int ans=0;
- for(int i=0;i<=n-r;i++)
- {
- for(int j=0;j<=m-c;j++)
- {
- ans=max(ans,vmax[i][j]-vmin[i][j]);
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }</span></strong>
原创是我可敬的师傅,搜索到的上面那个应该就是原文.
单调队列及其应用
单调队列，望文生义，就是指队列中的元素是单调的。如：{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。
单调队列的出现可以简化问题，队首元素便是最大（小）值，这样，选取最大（小）值的复杂度便为o（1），由于队列的性质，每个元素入队一次，出队一次，维护队列的复杂度均摊下来便是o（1）。
如何维护单调队列呢，以单调递增序列为例：
1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。
2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止
要特别注意头指针和尾指针的应用。
下面介绍单调队列的具体应用：
一、单调队列的直接应用
1.合并果子
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【输入文件】
输入文件fruit.in包括两行，第一行是一个整数n（1 <= n <= 10000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。
【输出文件】
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【样例输入】
3
1 2 9
【样例输出】
15
【数据规模】
对于30%的数据，保证有n <= 1000；
对于50%的数据，保证有n <= 5000；
对于全部的数据，保证有n <= 10000。
分析:
这个题目非常的经典，发放也很多，可以采用快排或者堆，其思想都是选取当前最小的两个堆进行合并。复杂度均为O(nlogn)，如果用有序队列维护，时间复杂度为O（n）。
每次选取进行合并的两堆，不是最先给定的堆，就是合并最初堆若干次后得到的新堆，所以需要维护两个单调递增队列，一个队列存最初给定的堆的值（1），一个存合并后得到的新值（2）。
每次选择时有三种状态：
1.选取队一的队首两个
2.选取队2的的队首两个
3.选取二者队首各一个
只需对每个队列的指针做相应的更改。
特别注意初始化。
这道题很好的运用了题目中决策的单调性，对初始对经行排序，保证了其单调性。而对于新产生的堆来说，一旦有新元素加入其中，则新元素一定大于原有元素。（很显然，由于队列1的单调性）。
也就是说，队列的单调性是自然而然的。是不需要维护的。要善于观察分析，才能发现。
1 program because_of_love; 2 var 3 a,b:array[1..100000] of longint; 4 h1,h2,t2,temp,n,i,ans:longint; 5 function min(a,b,c:longint):longint; 6 begin 7 if a<b then min:=a 8 else min:=b; 9 if c<min then min:=c; 10 end; 11 procedure sort(l,r:longint); 12 var 13 i,j,mid,temp:longint; 14 begin 15 i:=l; 16 j:=r; 17 mid:=a[l+random(r-l)];//随机化排序 18 repeat 19 while a[i]<mid do inc(i); 20 while a[j]>mid do dec(j); 21 if i<=j then 22 begin 23 temp:=a[i]; 24 a[i]:=a[j]; 25 a[j]:=temp; 26 inc(i); 27 dec(j); 28 end; 29 until i>j; 30 if i<r then sort(i,r); 31 if l<j then sort(l,j); 32 end; 33 begin 34 randomize; 35 readln(n); 36 for i:=1 to n do 37 read(a[i]); 38 for i:=1 to n do 39 b[i]:=maxlongint>>2;//保证程序在需要的地方停止，由于要选极小值 40 sort(1,n); 41 a[n+1]:=maxlongint>>2;//作用同上 42 a[n+2]:=maxlongint>>2; 43 h1:=1; 44 h2:=1; 45 t2:=0; 46 for i:=1 to n-1 do 47 begin 48 temp:=min(a[h1]+a[h1+1],a[h1]+b[h2],b[h2]+b[h2+1]); 49 if temp=a[h1]+a[h1+1] then inc(h1,2) 50 else if temp=a[h1]+b[h2] then begin inc(h1);inc(h2);end 51 else inc(h2,2); 52 inc(t2); 53 b[t2]:=temp; 54 inc(ans,temp); 55 end; 56 writeln(ans); 57 end.
2．Window
给定你n个数ai~an一个确定长度的区间，让你求出每个区间内的最大值，并按照顺序输出
输入
N，k
A1~an
输出
每个区间内的最大值
分析
由于该题的区间长度一定，我们可以用一个长度为k（A,B）的队列来维护数据的有序性。
剩下的问题就是如何维护队列的有序性了。
最前面已经说到了，代码也不再赘余。
3、志愿者选拔(foj 1894)
世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的人品是主要考查对象之一。（提高人品的方法有扶老奶奶过街，不闯红灯等）
作为主面试官的John想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个程序来计算。
Input
输入数据第一行为一整数T，表示有T组输入数据。
每组数据第一行为”START”，表示面试开始
接下来的数据中有三种情况：
1 C NAME RP_VALUE 名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)
2 G 排在面试队伍最前面的同学面试结束离开考场。
3 Q 主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。
最后一行为”END”，表示所有的面试结束，面试的同学们可以依次离开了。
所有参加面试的同学总人数不超过1,000,000
Output
对于每个询问Q,输出当前正在接受面试的队伍中人品最高的值,如果当前没有人正在接受面试则输出-1。
Sample Input
2
START
C Tiny 1000000000
C Lina 0
Q
G
Q
END
START
Q
C ccQ 200
C cxw 100
Q
G
Q
C wzc 500
Q
END
Sample Output
1000000000
0
-1
200
100
分析：
题目本身就是队列，由于要找的是最大值，我们自然想到用单调队列解决问题。
维护一个单调递减序列，只需输出序列中的第一个元素即可。
对于命令我们可以进行不同的处理：
如果是Q命令，则判断当前队列中是否仍有元素，如果没有则输出-1，如果有则直接输出队首。
如果是G命令，则对last加1，之后对于队列中所有超出范围的前端元素进行出队操作。（该元素在原序列中的位置>=last）
如果是C命令，则将该元素加入队列中，并和队尾元素比较，维护队列的单调性。
这里考虑一个问题，当前元素加如后对队尾元素为什么可以毫无保留的删去呢？
因为当前加入的元素比队尾元素大，且该元素比队尾元素入队晚（也就是该元素比队尾元素晚出队），所以只要该元素在队列中，就一定不会选取队尾元素。也就是当前状态一定比队尾元素的状态更优。——这里一定要理解深刻，这是队列的本质。
因此，这题的单调队列中维护的一个属性是元素的价值，一个属性是单调队列中的元素在原序列中的位置。
注意，q中的值是该元素在原序列中的位置！
1 program because_of_love; 2 var 3 a,q:array[0..1000000] of longint; 4 zu,i,l,r,last,tt,w:longint; 5 s:string; 6 begin 7 readln(zu); 8 for i:=1 to zu do 9 begin 10 tt:=0; 11 fillchar(a,sizeof(a),0); 12 readln(s); 13 l:=1; 14 r:=0; 15 last:=0; 16 while s<>'END' do 17 begin 18 readln(s); 19 case s[1] of 20 'G':begin 21 inc(last); 22 while (q[l]<=last)and(l<=r)do inc(l); 23 end; 24 'Q':begin 25 if l>r then writeln(-1) 26 else writeln(a[q[l]]); 27 end; 28 'C':begin 29 inc(tt); 30 delete(s,1,2); 31 w:=pos('',s); 32 delete(s,1,w); 33 val(s,a[tt]); 34 while(a[tt]>a[q[r]])and(l<=r)do dec(r); 35 inc(r); 36 q[r]:=tt; 37 end; 38 end; 39 end; 40 end; 41 end.
4、广告印刷
【问题描述】
最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，且0<Hi<=1,000,000,000，并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。
【输入文件】
中的第一行是一个数n (n<= 400,000 ）
第二行是n个数，分别表示每个建筑物高度H1,H2…HN，且0<Hi<=1,000,000,000。
【输出文件】
输出文件 ad.out 中一共有一行，表示广告牌的最大面积。
【输入样例】
6
5 8 4 4 8 4
【输出样例】
24
【分析】
最终的广告牌一定等于某个建筑物的高度×其能达到的最大长度
现在，建筑物的高度已知，现在只需要知道每个高度能达到的最大长度是多少。由于n是400000，我们只能用O（n）或O（nlogn）的算法。可以使用rmq，在后边的论文中会讲到。
现在讲时间复杂度为o（n）的单调队列的方法。
继续上边的思路，对于每个建筑物，只需要找到其能够扩展到的最大宽度即可。也就是这个建筑物的左右两边的比它低或等于它的建筑物个数。
如何用单调队列呢？
我们从1~n一次进队，维护一个单调递减序列。每次加入元素后维护其单调性，当然这样做必然会使一些元素出队，出队的元素一定要比当前加入的元素小，也就是说当前元素就是出队的元素能在右侧达到的最远的建筑物！
注意，要让h[n+1]=0并且让该元素入队一次（会使当前队列中的所有元素出队），保证每个元素都有其“右极限”的值。
要求“左极限”同理，只需从n~0循环即可，注意0
这道题是对单调队列的变形使用。由于问题的结果具有单调性，很好的利用出队元素的特性.
1 program because_of_love; 2 var 3 q:array[0..40000] of longint; 4 n,i,l,r,ans:longint; 5 h,left,right:array[0..40000] of longint; 6 begin 7 readln(n); 8 for i:=1 to n do 9 read(h[i]); 10 l:=1; 11 r:=0; 12 for i:=1 to n+1 do 13 begin 14 while (h[i]<h[q[r]])and(l<=r) do 15 begin 16 right[q[r]]:=i; 17 dec(r); 18 end; 19 inc(r); 20 q[r]:=i; 21 end; 22 l:=1; 23 r:=0; 24 for i:=n downto 0 do 25 begin 26 while (h[i]<h[q[r]])and(l<=r)do 27 begin 28 left[q[r]]:=i; 29 dec(r); 30 end; 31 inc(r); 32 q[r]:=i; 33 end; 34 for i:=1 to n do 35 if (right[i]-left[i]-1)*h[i]>ans then ans:=(right[i]-left[i]-1)*h[i]; 36 writeln(ans); 37 end.
5、总结
单调队列的应用仍有很多实例，这一不能一一道出。
首先考虑问题需要的时间复杂度如果是o（n）的算法，单调队列是首选。
其次要善于观察分析，发现题目中的单调性。决策的单调（合并果子），要求问题的特性（window），元素价值和其在原序列中位置的单调（志愿者），问题结果的单调（广告印刷）。
二、单调队列在优化动态规划中的应用
做动态规划时常常会见到形如这样的转移方程：
f[x] = max or min{g(k) | b[x] <= k < x} + w[x]
(其中b[x]随x单调不降，即b[1]<=b[2]<=b[3]<=...<=b[n])
(g[k]表示一个和k或f[k]有关的函数，w[x]表示一个和x有关的函数)
这个方程怎样求解呢？我们注意到这样一个性质：如果存在两个数j, k，使得j <= k，而且g(k) <= g(j)，则决策j是毫无用处的。因为根据b[x]单调的特性，如果j可以作为合法决策，那么k一定可以作为合法决策，又因为k比j要优，（注意：在这个经典模型中，“优”是绝对的，是与当前正在计算的状态无关的），所以说，如果把待决策表中的决策按照k排序的话，则g(k)必然是不降的。
这样，就引导我们使用一个单调队列来维护决策表。对于每一个状态f(x)来说，计算过程分为以下几步：
1、 队首元素出队，直到队首元素在给定的范围中。
2、 此时，队首元素就是状态f(x)的最优决策，
3、计算g(x)，并将其插入到单调队列的尾部，同时维持队列的单调性（不断地出队，直到队列单调为止）。
重复上述步骤直到所有的函数值均被计算出来。不难看出这样的算法均摊时间复杂度是O(1)的。因此求解f(x)的时间复杂度从O(n^2)降到了O(n)。
单调队列指一个队列中的所有的数符合单调性（单调增或单调减），在信息学竞赛的一些题目上应用，会减少时间复杂度
单调队列的每个元素一般会存储两个值：
1.在原数列中的位置（下标）
2.该元素在动态规划中的状态值（价值）
单调队列同时保证这两个值单调。
下面看几个优化的实例：
1、 烽火传递
描述 Description
烽火台又称烽燧，是重要的防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确的传递，在m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出的信号的代价，请计算总共最少需要话费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确的传递！！！
输入格式 Input Format
第一行有两个数n,m分别表示n个烽火台，在m个烽火台中至少要有一个发出信号。
第二行为n个数，表示每一个烽火台的代价。
输出格式 Output Format
一个数，即最小代价。
样例
5 3
1 2 5 6 2
4
时间限制 Time Limitation
各个测试点1s
注释 Hint
1<=n,m<=1,000,000
分析
要用动态规划的方法解决。我们可以写出这样的方程f[i]:=min{f[j]}+a[i]（i-m<=j<i-1）（因为要保证i之前的3个中必须存在被点亮的烽火台）。单纯这样循环会造成超时。
我们想到了用单调队列进行优化，由于随着i的循环，每次只有一个i进入决策区间也只有一个i出决策区间，由于每次选取决策区间中的最小值，所以维护一个单调递增序列，每次取出队首元素即可。
为什么可以将队尾元素无情的删去呢？由于后进队的序列同时满足在原序列中的位置更靠后和其在动态规划中的价值更大。这样选取这个元素就要比选取之前的任何一个决策要优，所以之前被删掉的决策都是无用的。
这道题的本质就是用单调队列维护了决策本身的价值和其在原序列中位置的同时单调。
要特别注意单调队列中的值是决策在原决策序列中的位置。
1 program because_of_love; 2 var 3 a,f,q:array[0..1000000] of longint; 4 m,n,l,r,i,ans:longint; 5 begin 6 readln(n,m); 7 for i:=1 to n do 8 read(a[i]); 9 f[0]:=0; 10 l:=1;r:=0; 11 for i:=1 to n do 12 begin 13 while(q[l]<i-m)and(l<=r)do inc(l); 14 while(f[i-1]<f[q[r]])and(l<=r)do dec(r); 15 inc(r); 16 q[r]:=i-1; 17 f[i]:=f[q[l]]+a[i]; 18 end; 19 ans:=maxlongint; 20 for i:=n downto n-m+1 do 21 if ans>f[i] then ans:=f[i]; 22 writeln(ans); 23 end.
2、难题的解决
给定一个序列，读入n,k和a1~an,让你求出该序列中包含第k项的最长上升子序列长度。
1<=n<=300000 k<=n
分析
不要被问题的表面现象迷惑，既然要包含第k项，那么在k项的左边，比第k项大
的元素一定不会进入目标序列。同理在k项的右边，比第k项小的元素一定也不会进入目标队列。
那么我们直接把这些无用的元素删去。
剩下的队列就好看得多。在k项之前的元素都比k小，之后的都比k项大。我们只需从1~k-1求一遍最长上升子序列，再从k+1~n求一遍最长上升子序列即可。最后结果为二者的值加1。
由于数据范围很大，用传统的n2算法无法完成任务。所以本题地关键是（nlogn）的lis
假如x<y<t且a[x]<a[y],f[x]=f[y],也就是说选取x，y都可以更新得到相同的的f[t]的值，那么选取谁呢。显然选取x会更优，因为在a[x]…a[y]中如果存在a[z],使得a[x]<a[z]<a[y]那么就可以通过x得到更长的最长不降子序列的值。
根据f的值进行分类，我们只需要保留满足f[t]=k的所有a[t]中的最小值，设d[k]记录这个值，即d[k]:=min{a[t]}(f[t]=k)
我们注意到d有两个特点：
1. d[k]的值在整个过程中是单调不上升的。
2. d数组是有序的。即d1<d2<….<dn
利用d，我们可以得到一种计算最长上升子序列的方法。设当前已经求出的最长上升序
列的长度为len，每次读入一个新元素x。
如果x>d[len]将其直接假如d，inc(len)得到更长的序列
否则，在d中查找到第一个比该元素小的元素d[k]，将该元素加入，d[k+1]:=x;如果使用
顺序查找效率会很低，所以采用二分查找，将其复杂度降为log级，难点在于二分查找。
本题中的单调队列的出现时利用决策的性质，用元素在动归中的价值分类。在入队操做
时并未让所有元素出队，而是直接插入相应位置，这是根据题目的特殊性决定的。对于一个单调的序列往往用二分法。
当然这种发法也可推广到其他的最XX序列问题
上面说的已经很详细，代码就省了。
三、一些总结
单调队列有很多的应用，这里只是介绍了一部分，特别是在优化动态规划时。
希望读者能在实践中形成自己的方法