单调栈 易理解版

static int[] l, r;//分别存储左右方向最小值点index

static final int n = 100010;
static long[] h = new long[n];//element

public static void main(String[] args)throws Exception{

    while(true){
        int len = nextInt();
        if(len==0) break;
        for(int i=0; i<len; i++) h[i] = nextInt();
        l = new int[len]; r = new int[len];
        l[0] = -1; r[len-1] = len;//哨兵 存储边界
        int i, j;
        Stack<Integer> st1 = new Stack<>();//单调栈
        Stack<Integer> st2 = new Stack<>();
        for(i=0, j=len-1; i<len; i++, j--){//遍历
            while(st1.size()!=0&&h[i]<=h[st1.peek()]) st1.pop();
            l[i] = st1.size()==0?-1:st1.peek();//若栈是空的 则左边界为-1 否则 是栈顶元素
            st1.push(i);//无论怎样 都得进栈
            // 从后向前 与上面一样 
            while(st2.size()!=0&&h[j]<=h[st2.peek()]) st2.pop();
            r[j] = st2.size()==0?len:st2.peek();
            st2.push(j);
        }
        long ans = 0;
        for(i=0; i<len; i++)
            ans = Math.max(ans, (r[i] - l[i] - 1)*h[i]);
        out.println(ans);
    }
    out.close();
}