1 题目描述

2 思路
1.用一个栈保存当前元素以前的序列，栈用一个数组来表示
2.栈中序列是单调递增的 当i<=j a[i]>=a[j]时,delete(a[i]) 保证剩余的序列一定是单调的

3 代码

package chapter02;

import java.io.IOException;
import java.util.Scanner;

/**
 * @author mys
 * @date 2022/3/21 17:44
 */
public class p830 {
    static int N = 100010;
    public static void main(String[] args) throws IOException {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//数组长度

        //栈
        int[] stk = new int[N];
        int tt = 0;

        for (int i = 0; i < n; i ++) {
            int x = input.nextInt();
            //栈不为空，同时栈顶元素>=x，出栈，保证栈是一个单调递减的栈
            while (tt != 0 && stk[tt] >= x) {
                tt --;
            }
            //如果栈不为空，输出栈顶元素，即比当前元素小的最近的元素，否则输出0
            if (tt != 0) {
                System.out.print(stk[tt] + " ");
            } else {
                System.out.print(-1 + " ");
            }
            //最后把当前元素把x加入到栈中
            stk[++ tt] = x;
        }
    }
}

单调栈leetcode题目：
84. 柱状图中最大的矩形

暴力解法：遍历高度，往左、右找第一个小于当前元素的位置（类似上面的单调栈），高度乘左右宽度就是的最大值就是所求结果。此写法在LC上能通过，但是时间、空间效率都很低，思路简单。

public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        //left:存放从当前元素位置往做左，直到比当前元素小
        //right:存放从当前元素位置往右，直到比当前元素小或到达右边界
        int[] left = new int[len], right = new int[len];
        Stack<Integer> stk = new Stack<>();

        //从左往右遍历:找左边第一个小于当前位置的元素
        for (int i = 0; i < len; i ++) {
            //如果栈不为空，同时栈顶元素>=当前元素，出栈，保证栈是一个单调递增的序列
            while (! stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
                stk.pop();
            }
            //如果栈不为空，记录栈顶元素，否则为-1
            if (! stk.isEmpty()){
                left[i] = stk.peek();
            } else {
                left[i] = -1;
            }
            //当前元素入栈
            stk.push(i);
        }

        //注意：清空栈
        stk = new Stack<>();

        //从右往左遍历：找右边第一个小于当前位置的元素，没有则是右边界
        for (int i = len - 1; i >= 0; i --) {
            while (! stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
                stk.pop();
            }
            if (! stk.isEmpty()) {
                right[i] = stk.peek();
            } else {
                right[i] = len;
            }
            stk.push(i);
        }

        int res = 0;
        //遍历上边界：找面积最大值
        for (int i = 0; i < len; i ++) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }

未完待续…