知识的遗忘率真是太高了。。所以就随便写一下 下面我们仅举单调上升的单调栈的例子，让读者(主要是我)对单调栈的实现有一定的概念。 单调栈是在序列上维护的，我们扫描这个序列 实现的方法是这样的:
while(sn&&x<=sta[sn]) --sn; sta[++sn]=x; a[sn]=i;其中sta表示栈中元素的大小，a表示栈中元素的位置,x表示当前元素,pos表示当前元素的位置。 就是当前的元素比栈尾小的时候总是弹出栈尾，在栈尾小于x的时候将x插在栈尾 单调栈的性质： 性质1：容易验证，对单调栈中的下标为i的元素，其必然为a[i]至pos-1中最小的，否则i必然已经被弹出。 性质2：同样的，sta[i]必然也是[a[i-1]+1,a[i]]中最小的，否则若该区间存在比sta[i]中更小的元素，其必然比sta[i-1]大，否则与性质1矛盾。则该元素大小在(sta[i-1],sta[i])之间，则其必然已经插入了栈，并使得i的下标后移一位。 容易验证，单调栈实际上表明了从某个点开始向左向右延伸，使其拓展到左边界-1即a[i-1]的元素sta[i-1]小于他，右边界+1即pos的元素x小于他。这说明如果一个题目要在序列上面进行min操作，单调栈可以直观的表示出一个元素可以“控制”的区间的范围。 写代码时可能会错误的地方： 在插入单调栈时元素的左边界已经显然了，但是右边界仅在该元素被弹出时确定。 对于序列已经处理完后，最后留在栈中未被弹出的元素一般需要退完栈。其控制的右边界显然为a[i]至n.
至此，我们得到了一个可以便捷的算出各个元素的控制区间的O(n)的算法
举一个栗子 有n个柱子，找出一个区间l,r使得min(h[i])*(r-l+1),l<=i<=r,最大化。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<string> #include<cstring> using namespace std; const int N=1000; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; int T,n,m,x,ans,res,last,u,v; int a[N],sta[N],sn; int pd; int main() { cin>>n; for(int i=1;i<=n;++i) { cin>>x; ans=max(ans,x); while(sn&&x<=sta[sn]) { ans=max(ans,(i-1-a[sn-1])*sta[sn]); --sn; } sta[++sn]=x; a[sn]=i; } while(sn) { ans=max(ans,(n-a[sn-1])*sta[sn]); --sn; } printf("%d",ans); }说实话这样子我有点害怕到时候代码查重判我抄网上的代码。（滑稽）
