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