单调栈，就是栈中的元素始终是单调递增的。
对于某类特殊的问题，若当前状态与下一状态的单调性有关，就必须使用单调栈。

题目描述
贤正的某 N 头奶牛 (1 <= N <= 80,000) 正在过乱头发节！由于每头牛都 意识到自己凌乱不堪的发型， 宁智贤希望统计出能够看到其他牛的头发的牛的数量。
每一头牛 i有一个高度 h[i] (1 <= h[i] <= 1,000,000,000)而且面向东方排成 一排(在我们的图中是向右)。因此，第i头牛可以看到她前面的那些牛的头， （即i+1, i+2,等等），只要那些牛的高度严格小于她的高度。
例如这个例子:

牛#1 可以看到她们的发型 #2, 3, 4 牛#2 不能看到任何牛的发型 牛#3 可以看到她的发型 #4 牛#4 不能看到任何牛的发型 牛#5 可以看到她的发型 6 牛#6 不能看到任何牛的发型!
让 c[i] 表示第i头牛可以看到发型的牛的数量；请输出 c[1] 至 c[N]的和。 如上面的这个例子，正确解是3 + 0 + 1 + 0 + 1 + 0 = 5。
输入格式
Line 1: 牛的数量 N。
Lines 2…N+1: 第 i+1 是一个整数，表示第i头牛的高度。
输出格式
Line 1: 一个整数表示c[1] 至 c[N]的和。
样例数据
input
6
10
3
7
4
12
2
output
5

对于这道题目，发现当一只新的奶牛进来后，比原来的奶牛要高，那么这只原来的奶牛无论如何也看不到什么牛，就属于无用状态，显然只有比新加入的奶牛高才能继续发挥统计答案的作用。因此，我们可以维护一个单调递减的序列：
当新加入的奶牛比栈顶的奶牛矮，答案加上top（表示原来的奶牛都看得到）
当新加入的奶牛比栈顶的奶牛高，把所有比它矮的奶牛从栈中弹出（改状态无用），答案加top（表示剩下的奶牛都能看得清这一只奶牛），并进栈。
算法原理理解后，就很好实现了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[100000],st[100000],top=0;
	long long ans=0;
	cin>>n;
	for (int i=1;i<=n;i++)cin>>a[i];
	for (int i=1;i<=n;i++)
	{
	    while (a[i]>=st[top]&&top>0) 
	    	top--;
	    ans+=top;
	    st[++top]=a[i];
	}
	cout<<ans;
	return 0;
} 

题目描述
　　Farmer John的牛们认为，太阳升起的那一刻是一天中最美好的，在那时她们 可以看到远方城市模糊的轮廓。显然，这些轮廓其实是城市里建筑物模糊的影子。 　　建筑物的影子实在太模糊了，牛们只好把它们近似地看成若干个边长为1单位 长度的正方体整齐地叠在一起。城市中的所有建筑物的影子都是标准的矩形。牛们 的视野宽W个单位长度(1<=W<=1,000,000)，不妨把它们按从左到右划分成W列，并 按1~W编号。建筑物的轮廓用N组(1<=N<=50,000)数给予描述，每组数包含2个整数 x、y(1<=x<=W,0<=y<=500,000)，表示从第x列开始，建筑物影子的高度变成了y。 （也就是说，第x[i]列到第x[i+1]-1列中每一列建筑物影子的高度都是y[i]个单位 长度）
　　贝茜想知道这座城市里最少有多少幢建筑物，也就是说，这些影子最少可以由 多少个矩形完全覆盖。当然，建筑物的影子可以有重叠。请你写一个程序帮她计算 一下。
题目描述2

对于这道题，我们可以这么想：
对于摆放的每一块积木，如果高度要比上一个矩阵高，那么必然多出一块矩阵；
如果高度比上一个矩阵低，必然上一个矩阵要多出来；如果高度相等，则当前高度可以补到前面的高度上面去。
因此，维护一个单调递增的栈：
1.比栈顶高，进栈。
2.比栈顶低，弹出比它高的矩阵，累加答案；继续进栈。
3.和栈顶一样高，什么都不做。

#include<bits/stdc++.h>
using namespace std;
int n,w,k,ans=0,a[600000]={},top=0,st[600000]={};
int main()
{
	cin>>n>>w;
	for (int i=1;i<=n;i++) cin>>k>>a[i];
	if (n==1&&a[1]==0)
	{
		cout<<0;
		return 0;
	}
	for (int i=1;i<=n;i++)
	{
		while (a[i]<st[top]&&top>0) 
		{
		    ans++;
		    top--;
		}//如果小，则把比它大的元素弹出 
		if (a[i]>st[top]) st[++top]=a[i];
	}
	cout<<ans+top;
	return 0;
}

这道题的解体思路和地平线大致相同：
对于每一个矩阵，如果下一个比它高，凸出的部分必然没有；因此我们只需要使用单调栈维护单调递增，再用另外一个数组维护这个方块的高度往左最多能够放下的宽度即可。

#include<bits/stdc++.h>
using namespace std;
#define maxn 100100
#define qword long long

int n;
int s[maxn];
int a[maxn];
int w[maxn];

inline void read(int &readnum)
{
	int s=0,w=1;char c=getchar();
	while (c<'0' || c>'9') {if (c=='-') w=-1;c=getchar();}
	while (c>='0' && c<='9') s=s*10+c-48,c=getchar();
	readnum=s*w;
}

inline void Mem(void)
{
	memset(a,0,sizeof(a));
	memset(w,0,sizeof(w));
	memset(s,0,sizeof(s));
}

void work(void)
{
	for (int i=1;i<=n;++i) read(a[i]);
	int t=0;
	qword ans=0;
	for (int i=1;i<=n+1;++i)
	{
		if (a[i]>=s[t]) w[++t]=1,s[t]=a[i];
		//高于栈顶，进栈 
		if (a[i]<s[t])
		{
			int sum=0;
			while (a[i]<s[t])
			//低于栈顶，出栈并统计方案数 
			{
				sum+=w[t];
				//累加当前矩阵的高度所能放的最大宽度 
				ans=max(ans,(qword)sum*s[t]);
				//用高度乘上宽度统计答案 
				t--;
				//弹出 
			}
			s[++t]=a[i],w[t]=sum+1;
			//进栈，标记当前高度最大能往左放几个格子 
		}
	}
	printf("%lldn",ans);
}

int main(void)
{
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	read(n);
	while (n)
	{
		Mem();
		work();
		read(n);
	}
	return 0;
}