HDOJ 1506 Largest Rectangle in a Histogram (笛卡尔树)

本文主要是介绍HDOJ 1506 Largest Rectangle in a Histogram (笛卡尔树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1506
题意:给出一个由 $n$ 条矩形组成的图形，每个矩形宽度均为 $1$ ，高度为 $h_i$ ，求该图形中最大的连续矩形面积。
在这里插入图片描述

笛卡尔树的典型题，在此学习一下笛卡尔树，参考博客：
https://www.cnblogs.com/CaptainSlow/p/9282507.html
https://blog.csdn.net/qq_41551359/article/details/82661138
笛卡尔树是由一个序列生成的树形数据结构，从键值上看是一个堆，而对某子树按照中序遍历又对应原序列的一段连续区间，且该区间满足键值均大于（小根堆）或小于（大根堆）该子树的根的键值。因此可以说从索引位置key来看，满足二叉搜索树的特性，从键值value来看，满足堆的性质。如下图可以很形象地看出笛卡尔树的性质。
在这里插入图片描述
对于该题就可以根据输入的序列构建一棵笛卡尔树（构建方法可利用单调栈在 $O (n)$ 的时间复杂度内完成，具体见上述参考博客），搜索每个节点，以该节点的键值作为高的矩形的面积就是以该节点为根的子树大小乘以它的键值。

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int MAXN=100010;
struct node{int val,id;node *par,*ls,*rs;node(int i=0,int v=0,node* l=NULL,node* r=NULL){id=i;val=v;ls=l;rs=r;}
};
node* build(int arr[],int siz)
{stack<node*> s;node *now,*next,*last;for(int i=0;i<siz;i++){next=new node(i,arr[i]);last=NULL;while(!s.empty()){if(s.top()->val<next->val){now=s.top();if(now->rs){now->rs->par=next;next->ls=now->rs;}now->rs=next;next->par=now;break;}last=s.top();s.pop();}if(s.empty()&&last){next->ls=last;last->par=next;}s.push(next);}while(!s.empty()){now=s.top();s.pop();}return now;
}
long long ans;
int dfs(node *p)
{if(p==NULL) return 0;int cnt;cnt=dfs(p->ls)+dfs(p->rs)+1;ans=max(1LL*cnt*p->val,ans);return cnt;
}
int main()
{int n;int a[MAXN];while(1){ans=0;scanf("%d",&n);if(n==0) break;for(int i=0;i<n;i++)scanf("%d",&a[i]);node* root=build(a,n);dfs(root);printf("%lld\n",ans);}return 0;
}