85. 最大矩形 (opens new window)

1.单调栈

问题转化：将原数组转化为矩形高度数组，定义height[ i ][ j ]为左侧以matrix[ i ][ j ]为起点的最大矩形高度。例如matrix数组【"1","1","1","0","1","1"】对应的高度数组为【1，2，3，0，1，2】。然后按列搜索整个高度矩阵(每一列都可以看作是一个朝向左侧的柱状图)，求出以每个元素作为矩形右边界的最大矩阵面积。从而将问题转化为了求出每一列能够勾勒的最大矩形面积，然后返回所有列结果的最大值。(1130. 叶值的最小代价生成树 | Blage's Coding (opens new window))

确定每个点搜索时生成矩形的生成方式也很关键，比如每次都搜索以该点作为左上角顶点的最大矩形。然而即便如此这对于解题依旧没有帮助，因为即使得到前一个顶点的结果，下一个顶点的宽度和高都是在同时变化的，所以矩形问题除了要有固定起始点的思维，还需要有定高的思想。

暴力时间复杂度O(m*m*n*n)缩减为O(m*n)

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int[][] heights=new int[matrix.length][matrix[0].length];
        for(int i=0;i<matrix.length;i++){
            int temp=matrix[i][0]=='1'?1:0;
            heights[i][0]=temp;
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[i][j]=='1'){
                    temp=matrix[i][j-1]=='1'?temp+1:1;
                    heights[i][j]=temp;
                }
                else{
                    temp=0;
                    heights[i][j]=temp;
                }
            }
        }
        //枚举找到每一列元素的最大值
        Deque<Integer> stack=new LinkedList<>();
        int[] upedg=new int[matrix.length];
        int[] downedg=new int[matrix.length];
        int res=0;
        for(int j=0;j<matrix[0].length;j++){
            stack.clear();
            stack.offerFirst(-1);
            for(int i=0;i<heights.length;i++){
                while(stack.peekFirst()!=-1&&heights[i][j]<=heights[stack.peekFirst()][j]) stack.pollFirst();
                upedg[i]=stack.peekFirst();
                stack.offerFirst(i);
            }
            stack.clear();
            stack.offerFirst(heights.length);
            for(int i=heights.length-1;i>=0;i--){
                while(stack.peekFirst()!=heights.length&&heights[i][j]<=heights[stack.peekFirst()][j]) stack.pollFirst();
                downedg[i]=stack.peekFirst();
                stack.offerFirst(i);
            }
            for(int i=0;i<heights.length;i++){
                int temp=heights[i][j]*(downedg[i]-upedg[i]-1);
                res=Math.max(res,temp);
            }
        }
        return res;
    }
}