leetcode单调栈经典例题——最大矩形

最大矩形

题目描述：

 

思路：写这道题之前，如果大家没有写过leetcode的84.柱状图中的最大矩形，大家可以移步看看

柱状图的最大矩形，把图中的1看作墙；

好了言归正传，看到这道题我相信大部分同学脑袋是蒙的，有点不知道如何下手的感觉，同学们不要慌，我们现在先看一下题目给出的这道例题，我们先不看原图，先看看这个怎么解

假设有一道题要我们求这个矩形只包含1的最大面积，大家会怎么写？

假设要我们求这个矩形呢？

又或者是这个矩形呢？相信大家看到这一定会有点思路，是的，我们求这个大矩形的最大面积就得把他高=1，高=2，高=3，高=4的时候的最大面积全计算出来，再进行比较，因为我们是不知道哪种情况下它具有最大面积的，所以我们只需要把这个二维数组转化为四个一维数组，再分别计算四个一维数组构成的矩形的最大面积！

现在知道为什么有必要去看一看那道 柱状图的最大矩形 了吧，这道题完全就是它的变种，我们拆分开后就可以利用单调栈去解决每一个矩形的最大面积！

注：这道单调栈仍旧可以加入哨兵，省略我们判断栈是否为空以及的步骤，以及出现遍历一次完成，栈中还有元素的情况！

进入代码：

public int maximalRectangle(char[][] matrix) {
    int len = matrix[0].length;
    int[] heights = new int[len + 2];
    heights[0] = -1;   //前置哨兵
    int max = 0;
    heights[len + 1] = -1;  //后置哨兵
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < len; j++) {
            if (matrix[i][j] == '1') heights[j + 1] += 1
            else heights[j + 1] = 0;
        }
        max = Math.max(max,maxArea(heights));
    }
    return max;
}
public int maxArea(int[] heights){
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    int max = 0;
    for (int i = 1; i < heights.length; i++) {
        while (heights[i] < heights[stack.peek()]){
            Integer curHeight = heights[stack.pop()];
            if (curHeight == 0) break;
            int width = i - stack.peek() - 1;
            max = Math.max(max,width * curHeight);
        }
        stack.push(i);
    }
    return max;
}

总结：又是一道经典的单调栈例题，这道题逻辑不难，难的是我们想到利用大矩形拆分成一个一个小矩形的思想