leetcode:85. Maximal Rectangle-蒲公英云

leetcode:85. Maximal Rectangle

Dear 丶 2022-07-15 23:56 247阅读 0赞

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

import java.util.Arrays;
public class Solution{
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Solution s = new Solution();
        char[][] matrix = new char[][] { { '1', '0', '1', '0', '0' }, { '1', '0', '1', '1', '1' },
                { '1', '1', '1', '1', '1' }, { '1', '0', '0', '1', '0' } };
        matrix = new char[][] { "10100".toCharArray(), "10111".toCharArray(), "11111".toCharArray(),
                "10010".toCharArray() };
        matrix = new char[][] { "01101".toCharArray(), "11010".toCharArray(), "01110".toCharArray(),
                "11110".toCharArray(), "11111".toCharArray(), "00000".toCharArray() };
        int ans = s.maximalSquare(matrix);
        System.out.println(ans);
    }
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
//      output(matrix);
        int ans = 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if ('0' == matrix[i][j]) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = 1;
                int min = Math.min(inBorad(i - 1, j, dp), inBorad(i, j - 1, dp));
                while(min > 0){
                    if(matrix[i - min][j - min] == '1'){
                        dp[i][j] = min + dp[i][j];
                        break;
                    }
                    -- min;
                }
                if (dp[i][j] > ans) {
                    ans = dp[i][j];
                }
            }
//           output(dp);
        }
        return ans * ans;
    }
    void output(int[][] dp) {
        for (int[] d : dp)
            System.out.println(Arrays.toString(d));
        System.out.println("===================================");
    }
    void output(char[][] dp) {
        for (char[] d : dp)
            System.out.println(Arrays.toString(d));
        System.out.println("===================================");
    }
    public int inBorad(int x, int y, int[][] dp) {
        return x >= 0 && y >= 0 ? dp[x][y] : 0;
    }
}
/**
 * 
 * 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
 * 
 */