题意：求一个直方图中最大矩形的面积。
很经典的一道问题了吧，可以用单调栈分别求出每个柱子左右两边第一个比它低的柱子（也就相当于求出了和它相连的最后一个比它高的柱子），确定每个柱子的左右边界，每个柱子的高度乘上左右边界的宽度求最大值就行了。
也可以用笛卡尔树上dp的方法搞一搞，即用每个结点权值和所在子树的大小分别表示高度和宽度。（建笛卡尔树的过程也用到了单调栈，作用是维护右链）
单调栈做法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+,inf=0x3f3f3f3f;
int a[N],n,sta[N],L[N],R[N],tp; int main() {
while(scanf("%d",&n)&&n) {
a[]=a[n+]=-;
for(int i=; i<=n; ++i)scanf("%d",&a[i]);
sta[tp=]=;
for(int i=; i<=n; ++i) {
for(; a[sta[tp]]>=a[i]; --tp);
L[i]=sta[tp]+,sta[++tp]=i;
}
sta[tp=]=n+;
for(int i=n; i>=; --i) {
for(; a[sta[tp]]>=a[i]; --tp);
R[i]=sta[tp]-,sta[++tp]=i;
}
ll ans=;
for(int i=; i<=n; ++i)ans=max(ans,(ll)a[i]*(R[i]-L[i]+));
printf("%lld\n",ans);
}
return ;
}
笛卡尔树做法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+,inf=0x3f3f3f3f;
int n,a[N];
struct Cartesian {
static const int N=1e5+;
int ls[N],rs[N],val[N],siz[N],sta[N],tp,tot;
int newnode(int x) {int u=tot++; ls[u]=rs[u]=siz[u]=,val[u]=x; return u;}
void build(int* a,int n) {
tot=,newnode(),sta[tp=]=newnode(-);
for(int i=; i<n; ++i) {
int u=newnode(a[i]);
for(; val[sta[tp]]>=val[u]; --tp);
ls[u]=rs[sta[tp]],rs[sta[tp]]=u;
sta[++tp]=u;
}
}
void dfs(int u=) {
if(!u)return;
dfs(ls[u]),dfs(rs[u]);
siz[u]=siz[ls[u]]+siz[rs[u]]+;
}
} cart; int main() {
while(scanf("%d",&n)&&n) {
for(int i=; i<n; ++i)scanf("%d",&a[i]);
cart.build(a,n);
cart.dfs();
ll ans=;
for(int i=; i<cart.tot; ++i)ans=max(ans,(ll)cart.siz[i]*cart.val[i]);
printf("%lld\n",ans);
}
return ;
}