链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1102
思路：
首先介绍下单调栈的功能：利用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置。时间复杂度为O(n)。
这道题要找最大的矩形的面积，我们可以假设i为矩形最低的高，那么对每一个i找到向左走第一个比他小的l[i]，和向右走第一个比他小的r[i]。
我们可以知道当前矩阵最大为：a[i] * (l[i]-1-(r[i]-1)+1);对所有i的值取最大的。
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int M = 1e5+;
ll a[M],l[M],r[M];
int main()
{
int n;
cin>>n;
for(int i = ;i <= n;i ++)
cin>>a[i];
stack<ll>s;
for(int i = ;i <= n;i ++){
while(s.size()&&a[s.top()]>=a[i]) s.pop();
if(s.empty()) l[i] = ;
else l[i] = s.top()+;
s.push(i);
}
while(!s.empty()) s.pop();
for(int i = n;i >= ;i --){
while(s.size()&&a[s.top()]>=a[i]) s.pop();
if(s.empty()) r[i] = n;
else r[i] = s.top()-;
s.push(i);
}
while(!s.empty()) s.pop();
ll ans = ;
for(int i = ;i <= n;i ++){
ll num = a[i]*(r[i]-l[i]+);
//cout<<i<<" "<<l[i]<<" "<<r[i]<<" "<<num<<endl;
ans = max(num,ans);
}
cout<<ans<<endl;
}