题目描述
找左边第一个比小的数,找右边第一个比自己小的数,就是扩展的最大范围
样例
import java.util.*;
public class Main{
static int N = 100010;
static int[] h = new int[N];
//存放h数组的下标
static int[] stk = new int[N];
//l[i], r[i]表示第i个矩形的高度可向两侧扩展的左右边界
static int[] l = new int[N];
static int[] r = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n > 0){
for(int i = 1; i <= n ; i++) h[i] = sc.nextInt();
//把左右边界设为-1
h[0] = h[n + 1] = -1;
int tt = 0;
stk[0] = 0;//放到-1的情况
for(int i = 1; i <= n; i ++)
{
while(h[stk[tt]] >= h[i]) tt --;
l[i] = stk[tt];
stk[++ tt] = i;
}
tt = 0;
stk[0] = n + 1;//放到-1的情况
for(int i = n; i > 0 ; i --)
{
while(h[stk[tt]] >= h[i]) tt --;
r[i] = stk[tt];
stk[++ tt] = i;
}
long res = 0;
for(int i = 1; i <= n; i ++) res = Math.max(res, (long)h[i] * (r[i] - l[i] - 1));
System.out.println(res);
n = sc.nextInt();
}
}
}