IT虾米网

最大矩形算法详解

luoye 2020年11月07日 编程语言 165 0

给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例:

输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

解:

这题参考了一个答案的解法,自己又写了一遍

参考这里,遍历每个点,求以这个点为矩阵右下角的所有矩阵面积。如下图的两个例子,橙色是当前遍历的点,然后虚线框圈出的矩阵是其中一个矩阵。

 

怎么找出这样的矩阵呢?如下图,如果我们知道了以这个点结尾的连续 1 的个数的话,问题就变得简单了。

 

 

 

首先求出高度是 1 的矩形面积,也就是它自身的数,如图中橙色的 4,面积就是 4。

然后向上扩展一行,高度增加一,选出当前列最小的数字,作为矩阵的宽,求出面积,对应上图的矩形框。

然后继续向上扩展,重复步骤 2。

按照上边的方法,遍历所有的点,求出所有的矩阵就可以了。

以橙色的点为右下角,高度为 1。

 

 

 

高度为 2。

 

 

高度为 3。

 

 

 

作者的java代码,自己写的比较挫就不放上来了

public int maximalRectangle(char[][] matrix) { 
    if (matrix.length == 0) { 
        return 0; 
    } 
    //保存以当前数字结尾的连续 1 的个数 
    int[][] width = new int[matrix.length][matrix[0].length]; 
    int maxArea = 0; 
    //遍历每一行 
    for (int row = 0; row < matrix.length; row++) { 
        for (int col = 0; col < matrix[0].length; col++) { 
            //更新 width 
            if (matrix[row][col] == '1') { 
                if (col == 0) { 
                    width[row][col] = 1; 
                } else { 
                    width[row][col] = width[row][col - 1] + 1; 
                } 
            } else { 
                width[row][col] = 0; 
            } 
            //记录所有行中最小的数 
            int minWidth = width[row][col]; 
            //向上扩展行 
            for (int up_row = row; up_row >= 0; up_row--) { 
                int height = row - up_row + 1; 
                //找最小的数作为矩阵的宽 
                minWidth = Math.min(minWidth, width[up_row][col]); 
                //更新面积 
                maxArea = Math.max(maxArea, height * minWidth); 
            } 
        } 
    } 
    return maxArea; 
}

 

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

跳跃游戏算法详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。