leetcode--Maximal Rectangle-蒲公英云

leetcode--Maximal Rectangle

水深无声 2021-10-25 12:42 314阅读 0赞

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

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if(row == 0) return 0;
        int column = matrix[0].length;
        int[][] consecutiveOnes = new int[row][column];
        for(int i = 0; i < row; ++i) {
            for(int j = 0; j < column; ++j){
                if(matrix[i][j] - '0' == 1){
                    if(j == 0) 
                        consecutiveOnes[i][j] = 1;
                    else 
                        consecutiveOnes[i][j] = consecutiveOnes[i][j - 1] + 1;
                }
                else
                    consecutiveOnes[i][j] = 0;
            }
        }
        //calculate the max area. we check each element of consecutiveOnes column by column 
        int maxArea = 0;
        for(int i = 0; i < column; ++i){
            for(int j = 0; j < row; ++j){
                if(consecutiveOnes[j][i] != 0){
                    int minWidth = consecutiveOnes[j][i];
                    int index = j;
                    while(index >= 0 && consecutiveOnes[index][i] != 0){
                        minWidth = Math.min(minWidth, consecutiveOnes[index][i]);
                        maxArea = Math.max(maxArea, minWidth * (j - index + 1));
                        --index;
                    }
                }
            }
        }
        return maxArea;
    }
}

Remark: the second part (to seek the max area) can be solved by method used in “largest rectangle histogram” problem. Therefore, there is an algorithm with time O(row * column).

转载于//www.cnblogs.com/averillzheng/p/3825713.html