74.Maximal Rectangle（数组中的最大矩阵）

Level：

Hard

题目描述：

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:

[

  ["1","0","1","0","0"],

  ["1","0","1","1","1"],

  ["1","1","1","1","1"],

  ["1","0","0","1","0"]

]

Output: 6

思路分析：

我们的解题思路可以转换成求解Largest Rectangle in Histogram这道题的思路，假设有一个二维数组：

1 1 0 1 0 1

0 1 0 0 1 1

1 1 1 1 0 1

首先初始height数组为1 1 0 1 0 1，它是二维数组第一行的复制，然后我们很容易得到最大的面积为2，然后我们升级数组，我们扫描第二行，当我们遇到matrix[1] [i]为0时，我们设置height[i]为0，否则设置height[i]=height[i]+1；这意味着height增加了1，因此height数组变成了0 2 0 0 1 2。此时最大的面积也为2。应用同样的方法直到扫描完整个数组，最后height数组为 2 4 2 2 0 4，因此最大的矩阵面积为2*4=8。

代码：

public class Solution{

    public int maximalRectangle(char [][]matrix){

        if(matrix==null||matrix.length==0)

            return 0;

        int []height=new int [matrix[0].length]; //构造高度数组

        for(int i=0;i<matrix[0].length;i++){

            if(matrix[0][i]=='1')

                height[i]=1;

            else

                height[i]=0;

        }

        int res=largestarea(height);

        for(int i=1;i<matrix.length;i++){

            resetheight(matrix,height,i); //更新高度数组

            res=Math.max(res,largestarea(height)); //更新最大的矩形面积

        }

        return res;

    }

    public void resetheight(char[][]matrix,int []height,int i){

        for(int j=0;j<matrix[0].length;j++){

            if(matrix[i][j]=='1')

                height[j]=height[j]+1;

            else

                height[j]=0;

        }

    }

    public int largestarea(int []height){

        if(height==null||height.length==0)

            return 0;

        Stack<Integer>s=new Stack<>();

        int  maxarea=0;

        for(int i=0;i<=height.length;i++){

            int h=(i==height.length)?0:height[i]; //最后添加一个零是为了能让栈中最后一个元素弹出

            if(s.isEmpty()||h>=height[s.peek()]){

                s.push(i);

            }else{

                int temp=s.pop();

                maxarea=Math.max(maxarea,height[temp]*(s.isEmpty()?i:(i-s.peek()-1)));

                i--;

            }

        }

        return maxarea;

    }

}

巴特西

74.Maximal Rectangle（数组中的最大矩阵）

Level：

题目描述：

思路分析：

代码：

最新文章

热门文章