【算法】lc两道单调栈的应用

单调栈最经典的应用就是 找到数组中某个数左边第一个比它小的数

回顾回顾模板

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

这两道题就是典型应用

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

对于第一题，维护一个单调递增的栈，当枚举到当前柱子时，若栈顶元素的值比它大，则将栈顶元素pop出，直到栈顶元素的值小于等于它为止，则栈顶元素记录的就是左边第一个比它小的元素的位置，最后把当前元素加入到栈中，继续维护栈的单调性找出该柱子左边第一个比他矮的柱子，下标相减即使最大矩形的宽度。即可求出答案。

对于第二题，这题是上题的pro版本，需要我们手动求出每个柱子的高度，

我们用h[i][j]表示改点往上的最大连续1的高度

如果m[i][j] == '1' 则h[i][j] = h[i - 1][j] + 1;

然后我们去枚举每一个水平线，通过上一题的方式就能求出以当前水平线的最大矩形面积

code1

class Solution {
    public int largestRectangleArea(int[] h) {
        Stack<Integer> stk = new Stack<>();
        int n = h.length;
        int[] left = new int[n];
        int[] right = new int[n];

        //找到左边第一个比i小的数的位置
        for(int i = 0;i < n; i ++){
            while(!stk.isEmpty() && h[stk.peek()] >= h[i])stk.pop();
            if(stk.isEmpty())left[i] = -1; //左边没有比i小的数
            else left[i] = stk.peek();
            stk.push(i);
        }

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

        //找到右边第一个比i小的数的位置
        for(int i = n - 1; i >= 0; i --){
            while(!stk.isEmpty() && h[stk.peek()] >= h[i])stk.pop();
            if(stk.isEmpty())right[i] = n; //左边没有比i小的数
            else right[i] = stk.peek();
            stk.push(i);
        }
        //枚举每个高度
        int res = 0;
        for(int i = 0; i < n; i ++){
            res = Math.max(res,h[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
}

code2

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if(n == 0)return 0;
        int m = matrix[0].length;

        int[][] h = new int [n][m];

        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j ++){
                if(matrix[i][j] == '1'){
                    if(i > 0)h[i][j] = h[i - 1][j] + 1;
                    else h[i][j] = 1;
                }
                    
                
               
            }
        }
        int res = 0;

        //枚举每一水平线
        for(int i = 0; i < n; i ++){
            res = Math.max(res,largestRectangleArea(h[i]));
        }
        return res;
    }

    public int largestRectangleArea(int[] h) {
        Stack<Integer> stk = new Stack<>();
        int n = h.length;
        int[] left = new int[n];
        int[] right = new int[n];

        //找到左边第一个比i小的数的位置
        for(int i = 0;i < n; i ++){
            while(!stk.isEmpty() && h[stk.peek()] >= h[i])stk.pop();
            if(stk.isEmpty())left[i] = -1; //左边没有比i小的数
            else left[i] = stk.peek();
            stk.push(i);
        }

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

        //找到右边第一个比i小的数的位置
        for(int i = n - 1; i >= 0; i --){
            while(!stk.isEmpty() && h[stk.peek()] >= h[i])stk.pop();
            if(stk.isEmpty())right[i] = n; //右边没有比i小的数
            else right[i] = stk.peek();
            stk.push(i);
        }
        //枚举每个高度
        int res = 0;
        for(int i = 0; i < n; i ++){
            res = Math.max(res,h[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
}