这道题也是牛客网上的面试题，如果联想不到单调栈，就只能暴力做（数据范围1000 最多计算次 应该也能过,但我没试）。而使用了单调栈就可以优化成的复杂度

单调栈模板

求每一个数左边第一个比他小的数

public class Main{
    static int N = 100010,t = -1;
    static int a[] = new int[N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 0 ; i < n ; i ++) {
            int x = scanner.nextInt();
            while(t!=-1&&a[t]>=x) t--;
            System.out.print((t==-1?t:a[t])+" ");
            a[++t] = x;
        }
    }
}

最大的矩形

public class Main{
    static int N = 1010,t = -1,max,l;
    static int a[] = new int[N];
    static int s[] = new int[N];//用来存储每一个矩形的高度
    static int p[] = new int[N];//用来存储每一个矩形的下标
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 1; i <= n ; i ++) a[i] = scanner.nextInt();
        for(int i = 1 ; i <= n ; i++) {
            while(t!=-1&&s[t]>=a[i]) {
                l = t==0?0:p[t-1];
                max = Math.max(max, s[t]*(i-l-1));
                t--;
            }
            s[++t] = a[i];p[t] = i;
        }
        while(t!=-1) {
            l = t==0?0:p[t-1];
            max = Math.max(max, s[t]*(n-l));
            t--;
        }
        System.out.println(max);
    }
}