HISTOGRA - Largest Rectangle in a Histogram

HISTOGRA - Largest Rectangle in a Histogram

悬线法裸题。

题意

从 $1$ 到 $n$ 每个位置有一个高度为 $h_i$，宽度为 $1$ 的矩形。

求所有矩形覆盖面积中最大子矩形。

Sol

考虑单调栈思想，我们令 $pre_i$ 表示以 $h_i$ 为高度，从位置 $i$ 最多能向左拓展到的位置，即满足 $\forall j\in[pre_i,i]$ 都有 $h_j\geq h_i$ 且 $h_{pre_i-1}<h_i$。同理我们可以得到 $nxt_i$ 表示以 $h_i$ 为高度，从位置 $i$ 最多能向右拓展到的位置。

那么答案即 $\forall i\in[1,n],\max\{(nxt_i-pre_i+1)\cdot h_i\}$。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=1e5+1e1;
const lint INF=1e18+1e9;

lint h[MAXN],pre[MAXN],nxt[MAXN],Ans;
int n;

int main(void){
	
	n=readint;
	while(n){
		memset(h,0,sizeof(h));
		for(int i=1;i<=n;i++) h[i]=readlint;
		for(int i=1;i<=n;i++) pre[i]=nxt[i]=i;
		for(int i=1;i<=n;i++) while(pre[i]>1 && h[pre[i]-1]>=h[i]){
			pre[i]=pre[pre[i]-1];
		}
		for(int i=n;i;i--) while(nxt[i]<n && h[nxt[i]+1]>=h[i]){
			nxt[i]=nxt[nxt[i]+1];
		}
		for(int i=1;i<=n;i++) Ans=max((nxt[i]-pre[i]+1)*h[i],Ans);
		printf("%lld\n",Ans);
		n=readint,Ans=0;
	}

	return 0;
}