leetcode:85. Maximal Rectangle

Dear 丶 2022-07-15 23:56 146阅读 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
     * 
     */