AcWing 131. 直方图中最大的矩形(java---单调栈)
原题链接
简单
作者:
CYHMMZDAN
,
2023-03-21 20:07:47
,
所有人可见
,
阅读 123
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class Main {
static long[] a=new long[1000005];
static long[] b=new long[1000005];
static int[] c=new int[200005];
static int[] d=new int[200005];
static int[] e=new int[200005];
static int[] f=new int[200005];
static int t=520;
static int ans=0;
static int max=-1;
static int min=(int)2e+9;
static int n=0;
static int m=0;
static HashMap<Integer,Integer> map=new HashMap<>();
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while ((n=sc.nextInt())!=0) {
for(int i=1;i<=n;i++) {
d[i]=sc.nextInt();
}
d[0]=d[n+1]=-1;
t=0;
f[t]=0;
for(int j=1;j<=n;j++) {
while(d[f[t]]>=d[j]) {
t--;
}
c[j]=j-f[t];
f[++t]=j;
}
t=0;
f[t]=n+1;
for(int j=n;j>=1;j--) {
while(d[f[t]]>=d[j]) {
t--;
}
e[j]=f[t]-j;
f[++t]=j;
}
long max=0;
for(int i=1;i<=n;i++) {
max=Math.max(max,(long)d[i]*(c[i]+e[i]-1));
}
System.out.println(max);
}
}
}