单调栈为栈结构，可O(N)求出数组中每个元素向两边所能扩展到的最大长度，满足扩展到的每个元素均大于(或小于)此元素。
单调栈遵循严格递增或递减。
以严格递减为例。
数组L[i]、R[i]记录i点最多能扩展到的左端点与右端点；
在元素x入栈时，将栈顶小于x的元素弹出，并令R[top]=x的位置
令L(x的位置)=栈顶元素的位置。
以下为扩展两边小于等于当前节点的program.
const int MAXN=3000000+10,MAXINT=2147483640;
int n;
int L[MAXN],R[MAXN],zan[MAXN]={MAXINT},zp[MAXN]={0},top=0;//zan数组为人工栈 zp[i]记录zan[i]在数组中的位置
int in_it(int p,int x)//插入一个元素x 在数组中位置为p.
{
while(top>=0)
{
if(zan[top]<x)
{
R[zp[top]]=p-1;
top--;
}
else break;
}//修改小于x的元素的右端点
L[p]=zp[top]+1;//修改x的左边界
zan[++top]=x;
zp[top]=p;//将x压入栈中
}
read(n);
for (int i = 1, j = 0; i <= n; i++)
{
read(j);
in_it(i,j);
}
in_it(n+1,MAXINT);
在单调栈首尾input一个+∞，方便处理边界。
原文：http://www.cnblogs.com/jszyxw/p/4859602.html