单调栈练习（三）— 最大矩形

题目
同样是LeetCode原题：题目链接
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

暴力解
先来看一下暴力解的时间复杂度。
假如一个N * N的大矩阵，想要枚举出来所有的子矩阵时间复杂度是多少？ $O(N^4)$
是这样算的：
在N * N中随便点一个点A的可能性是$O(N^2)$种，再随便点一个点B，同样也是$O(N^2)$种可能性。
这两个点，一个在左上角，一个在右下角，就能够构成一个子矩阵，整体的时间复杂度是$O(N^4)$。

就算是点的点重复，那也只是重复了一次，不影响结果。所以枚举所有子矩阵的整体时间复杂度为$O(N^4)$。

整个暴力解的思路就是，先用4个for循环枚举出来所有的子矩阵（时间复杂度为$O(N^4)$）,再验证所有的子矩阵中的值是否都是1，并求出最大值。时间复杂度$O(N^2)$。整个暴力解的时间复杂度为$O(N^6)$。

单调栈
单调栈用到了一个技巧：压缩数组 。优化下后的整体时间复杂度是$O(N^2)$。

数组压缩的技巧可以将给定的二维数组构建成自己想要的柱状图，并利用单调栈，弹出当前栈顶元素，以当前栈顶元素的值为子矩阵中统一的高，并且找到左右区间最近且小的值作为边界，根据中间部分符合条件的值求出其最大面积，这部分具体可以看上一篇文章，可以说是一毛一样柱状图中最大的矩形。

在遍历给定的二维数组并构建压缩数组的过程中，如果 arr[i] [j] 和 arr[i + 1] [j] 位置的值都为1，则压缩完的数组中arr[j] 位置的值应该进行累加为2，如果中间断掉为0，则构建出来的柱状图对应的位置为0。

这样就能求出以二维数组中的每一行为底、每一行的每一个为子矩阵的高的每一个子矩阵的面积是多少。
遍历完整个二维数组后，最大面积也就求出来了。

代码
二维数组每遍历完一行，就求一次以当前行为底的所有子矩阵的最大面积。
maxRecFromBottom和上一篇帖子的解题思路一样柱状图中最大的矩形。

 public static int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix[0].length == 0){
            return 0;
        }
        int N = matrix[0].length;
        int M = matrix.length;
        int[] helpArr = new int[N];
        Integer max = Integer.MIN_VALUE;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                helpArr[j] = matrix[i][j] == '0' ? 0 : helpArr[j] + 1;
            }
              max = Math.max(max,maxRecFromBottom(helpArr));
        }

        return max;
    }

    public static int maxRecFromBottom(int[] height) {
        Stack<Integer> stack = new Stack<>();
        Integer max = Integer.MIN_VALUE;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] < height[stack.peek()]) {
                Integer cur = stack.pop();
                Integer leftMin = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max,(i - leftMin - 1) * height[cur]);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            Integer cur = stack.pop();
            Integer leftMin = stack.isEmpty() ? -1 : stack.peek();
            max = Math.max(max,(height.length - leftMin - 1) * height[cur]);
        }
        return max;
    }