单调队列及其应用
? 单调队列即队列内元素单调递增或递减，删除数据可以在队头或者队尾，加入元素只能在队尾加入。
? 由于单调队列的队头一定是最小值，故查询为O(1)；每个元素最多进队一次，出队一次，摊排分析下来仍然是O(1).
?
例1. 广告印刷
【问题描述】
最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N(N<=400000)个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，0<Hi<=1,000,000,000，并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。
【输入样例】
6
5 8 4 4 8 4
【输出样例】
24
【分析】
??? 这道题目是要求每个建筑物向左向右能扩展到的最大宽度，即左右两边比它高的连续的宽度。显然暴力枚举O(n^2)的复杂度是不可行的。
??? 考虑构造一个单调非递减队列，从左至右，依次加入到队列中，肯定会有元素出队列，设当前要插入的数为a，要出队列的数为b，必有b>=a，则b向右能到达的最远距离就是b-a。注意在求解时，让0先入队列，这样保证每个数据都会出队列。同理，左极限也可求出。
例2. POJ2823
【题意】
移动区间(长度固定)最值问题。
【分析】
??? 这类思想在单调队列优化思想中尤其重要：区间长度为k，求区间内的最大值，考虑第i个数和第j个数，j-i<k，若a[i]<a[j]，那么a[i]将毫无用处。直觉上理解，因为窗口的移动，a[i]要比a[j]先移出去，无论如何，区间的最大值都不可能是a[i]。
??? 这样，考虑构造一个单调递增的队列，存放相应的序号，当a[队尾]>=要入队数据a[i]，删除队尾元素；当队头<=i-k时，删除队头元素。
?
/**题意:由n(10^6)个数据组成的圆环,数据为1和-1,问从一个点开始顺时针或逆时针,能遍历完所有点,并且保证中间过程中sum>=0。分析:首先暴力O(n^2)是不可行的。 假设从i点开始,这里仅考虑向左,必须保证sum(j,i)>=0, i-n <j <= i. 设sum[i]表示从0到i点的和,即保证sum[i]-sum[j]>=0,即sum[i] - max(sum[j])>=0. 要求区间[i-n,i-1]最大值,维护单调递减队列即可。*/#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int N = 2100000;int n;char a[N/2];int num[N];int sum[N];int que[N/2];bool f[N/2],f2[N/2];void solve(bool t){ int i; int head=1,tail=0; for(i = 1; i < n; i++) { while(head<=tail&&sum[que[tail]]<=sum[i]) tail--; tail++; que[tail] = i; } for(i = n; i <= 2*n; i++) { while(head<=tail&&que[head]<i-n) head++; while(head<=tail&&sum[que[tail]]<=sum[i]) tail--; tail++; que[tail] = i; if(sum[i]-sum[que[head]]>=0) { if(t) f[i-n] = true; else f2[i-n] = true; } }}int main(){ int i; int t; int cases = 0; scanf("%d",&t); while(t--) { memset(f,0,sizeof(f)); memset(f2,0,sizeof(f2)); sum[0] = 0; scanf("%s",a+1); n = strlen(a+1); for(i = 1; i <= n; i++) { if(a[i]=='C') num[i] = 1; else num[i] = -1; } for(i = 1; i <= n; i++) num[i+n] = num[i]; for(i = 1; i <= n*2; i++) sum[i] = sum[i-1] + num[i]; //1234512345 int result = 0; solve(true); //reverse for(i = 1; i <= n; i++) sum[i] = sum[i-1] + num[n+1-i]; for(i = n+1; i <=2*n; i++) sum[i] = sum[i-1] + num[2*n+1-i]; //5432154321 solve(false); result = 0; for(i = 0; i < n; i++) if(f[i]||f2[n-i]) result++; printf("Case %d: %d\n",++cases,result); } return 0;}?
?
?