这道题好眼熟…
igronemyk 大神犇 今年4月份蛤理工“尚学堂杯”的时候就学会了，而我现在才 AC …无限膜拜
题意
每个木板宽度都为 1，木板按输入时顺序排列，求最大矩形面积。
基础知识
单调栈
顾名思义，单调栈，首先是一个栈，且栈内元素有单调性，单调栈的维护也很简单，只要在加入元素的时候暴力弹栈维护单调性即可。
解法
大致思路
考虑到单调栈的单调性（废话），可以 以矩形的高 为顺序维护一个单调增的栈，栈内类型为pair<long long,long long>。
对每次处理的情况分类讨论
- 如果栈为空，则将
pair(v[i],1)压入栈中。 - 如果加入
v[i]仍能保持单调性，则将pair(v[i],1)压入栈中。 - 否则，弹栈至 加入
v[i]时能保持单调性，再将pair(v[i],x)压入栈中。（x 为从 i 位置向左能延伸的最大宽度）
前两种情况很好处理，但第三种情况就比较难处理。求 x 的过程会增加一层复杂度，那么 x 怎么求？
求 x
懒得写了。。。见 POJ2559 最大矩形面积
高度为1的元素准备进栈，但必须从栈顶开始删除高度大于或等于1的矩形，因为2已经不可能延续到当前矩形。删除（2，1）这个元素之后，更新最大矩形面积为2*1=2，然后把它的宽度1累加到当前高度为1的准备进栈的矩形，然后进栈，当前栈为（1，2）
高度为1的元素准备进栈，删除（5，1）这个元素，更新最大矩形面积为51=5，把1累加到下一个元素，得到（4，2），删除（4，2），更新最大矩形面积为42=8，把2累加到下一个元素，得到（1，4），1*4=4<8，不必更新，删除（1，4），把4累加到当前准备进栈的元素然后进栈，当前栈为（1，5）
代码
#include <stack>
#include <iostream>
#include <vector>
using namespace std;
struct mypair
{
int length;
int width;
mypair() {}
mypair(int _length,int _width)
{
length=_length;
width=_width;
}
};
typedef mypair pint;
int main()
{
ios::sync_with_stdio(false);
int n;
while(cin>>n&&n!=0)
{
stack<pint>st;
vector<long long>v(n+2);
for(int i=1; i<=n; ++i)
{
cin>>v[i];
}
long long maxarea=-1;
v[n+1]=0;
for(int i=1; i<=n+1; ++i)
{
if(st.empty())
{
st.push(mypair(v[i],1));
}
else
{
if(v[i]>st.top().length)
{
st.push(mypair(v[i],1));
}
else
{
long long width=0;
while(!st.empty()&&st.top().length>=v[i])
{
width+=st.top().width;
if(width*st.top().length>maxarea)
{
maxarea=width*st.top().length;
}
st.pop();
}
st.push(mypair(v[i],width+1));
}
}
}
cout<<maxarea<<endl;
}
}