单调栈解决的是以某个值为最小（最大）值的最大区间，实现方法是：求最小值（最大值）的最大区间，维护一个递增（递减）的栈，当遇到一个比栈顶小的值的时候开始弹栈，弹栈停止的位置到这个值的区间即为此值左边的最大区间；同时，当一个值被弹掉的时候也就意味着比它更小（更大）的值来了，也可以计算被弹掉的值得右边的最大区间。
下面给出单调栈的类型及它所对应的求的东西
单调不升：该区间左边的数严格小于它，右边的数小于等于它
单调不降：该区间左边的数严格大于它，右边的数大于等于它
单调上升：该区间左边的数大于等于它，右边的数严格大于它
单调下降：该区间左边的数小于等于它，右边的数严格小于它
该代码求以给出的每个值为最大值的最大区间的左右端点。（该区间左边的数严格小于它，右边的数小于等于它）
#include<iostream> #include<cstdio> using namespace std; const int INF=2147483647,maxn=10000; int a[maxn+2],top=0,st[maxn+2],l[maxn+2],r[maxn+2],n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); a[n+1]=INF-1;a[0]=INF;st[++top]=0; for(int i=1;i<=n+1;i++) { while(a[i]>a[st[top]]) { l[st[top]]=st[top-1]+1;r[st[top]]=i-1; top--; } st[++top]=i; } for(int i=1;i<=n;i++)printf("%d %d ",l[i],r[i]); return 0; }
单调队列解决的是区间最小（最大）值，实现方法是：求区间最小（最大）值，就维护一个递增的双端队列，队中保存原始序列的标号，当即将入队的元素的值比队尾的元素的值小（大）的时候就不断弹掉队尾，知道出现比它更小的值，当即将入队的元素队首元素的跨度（即将入队元素的序号到队首元素序列的区间）大于规定区间时就不断弹掉队首，直到跨度小于或等于所规定的区间。如此可保证队首元素为最小（最大）值，（但不能保证队尾就是原始序列中的最大（最小）值），并维护区间长度。
单调不降（或上升）：区间最小值
单调不升（或下降）：区间最大值
那么，我们来一些拓展：二维单调队列
以下题为例
主持人（anchorman）
【题目描述】
小W是这次献祭的主持人。为了举行献祭，他先亲自去掀翻小C的棋盘，所以他就把布置场地的任务交给了你。有一片N行M列的网格土地，每一格都有一个XY值cij。你需要挑选出其中一块A行B列的土地作为献祭场地。我们定义一块土地的不稳定度为这块土地中最大的XY值和最小的XY值的差，为了保持均衡，要求挑选的场地的不稳定度尽可能小。小W希望你求出这个最小值，并统计有多少块场地满足这个最小值。
【输入数据】
第一行四个正整数N,M,A,B。
接下来N行，每行M个整数，表示一个XY值矩阵。
【输出数据】
输出一行两个整数，用空格隔开，表示选择的场地中最小的不稳定度和满足最小值的场地数。
【样例输入】
2 3 1 2
1 3 2
1 4 2
【样例输出】
1 1
【数据范围】
对于10%的数据，N,M<=10；
对于30%的数据，N,M<=100；
对于50%的数据，N,M<=500；
另外10%的数据，0<=cij<=1；
另外10%的数据，|cij|<=5；
对于100%的数据，1<=N,M,A,B<=1000，A<=N，B<=M，
|cij|<=10^9。
【样例解释】
选择土地(1,2)~(1,3)，最大为3，最小为2，相差为1。
题意：找一个A行B列的矩形，使得该矩形内的最大值减最小值最小
怎么做？
我们发现区间长度固定。单调队列！（但好像是个二维的来着）
我们用he[i][j][0/1]表示从i行j列开始的往右B个数的最小值（0）和最大值（1）
显然，这可以简单的在n行上个做一次单调队列求出。
我们用s[i][j][0/1]表示以i行j列为A*B的矩形的右上角顶点的矩形的最小值（0）和最大值（1）
由于我们已知he[i][j][0/1]，则s[i][j][0/1]=max or min(he[k][j][0/1])(i<=k<=i+A-1)
这个怎么求呢？当然是对于每一列，再来一次单调队列。
于是我们遍历每个点，计算出以它为右上角的A行B列的矩形的最大值和最小值的差，然后更新答案。
注意，矩形的左上角的行只能循环到n-A+1，列只能循环到m-B+1，否则根本就不会有一个A行B列的矩形
时间复杂度O(nm) （可能常数有点大）
#include<iostream> #include<cstdio> using namespace std; int he[1001][1001][2],s[1001][1001][2],a[1001][1001]; int que[1100],que2[1100]; int n,m,A,B; int Min=1999999999,tot=0; int main() { // freopen("anchorman.in","r",stdin);freopen("anchorman.out","w",stdout); scanf("%d%d%d%d",&n,&m,&A,&B); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) { int h=0,t=-1,h2=0,t2=-1; for(int j=m;j>=1;j--) { while(h<=t&&a[i][que[t]]>a[i][j])t--; que[++t]=j; while(que[h]>=j+B)h++; he[i][j][0]=a[i][que[h]]; while(h2<=t2&&a[i][que2[t2]]<a[i][j])t2--; que2[++t2]=j; while(que2[h2]>=j+B)h2++; he[i][j][1]=a[i][que2[h2]]; } } for(int j=1;j<=m;j++) { int h=0,t=-1,h2=0,t2=-1; for(int i=n;i>=1;i--) { while(h<=t&&he[que[t]][j][0]>he[i][j][0])t--; que[++t]=i; while(que[h]>=i+A)h++; s[i][j][0]=he[que[h]][j][0]; while(h2<=t2&&he[que2[t2]][j][1]<he[i][j][1])t2--; que2[++t2]=i; while(que2[h2]>=i+A)h2++; s[i][j][1]=he[que2[h2]][j][1]; } } for(int i=1;i<=n-A+1;i++) for(int j=1;j<=m-B+1;j++) { if(s[i][j][1]-s[i][j][0]==Min)tot++; if(s[i][j][1]-s[i][j][0]<Min){Min=s[i][j][1]-s[i][j][0];tot=1;} } cout<<Min<<" "<<tot<<endl; return 0; }