My accepted code. Is it O(n^3) solution?


  • 0
    X

    The idea is that: first calculate the consecutive '1's per row until the target position. Therefore:
    dp[i][j] = k when there are k consecutive '1's from dp[i][j-k+1] to dp[i][j]
    Then, for each (i,j), dp[i][j] means the bottom edge of the rectangle, and then look up, to add each possible dp[k][j](k = 0...i-1), and compare with the max.

    Here is the code:

    public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0)
            return 0;
        
        int row = matrix.length;
        int col = matrix[0].length;
        int max = 0;
        
        int[][] dp = new int[row][col];
        
        // initialize dp to have dp[i][j] = k when there are k consecutive '1's from dp[i][j-k+1] to dp[i][j]
        
        for (int i = 0; i < row; i++){
            if (matrix[i][0] == '1')
                dp[i][0] = 1;
        }
        
        for (int i = 0; i < row; i++){
            for (int j = 1; j < col; j++){
                if (matrix[i][j] == '1')
                    dp[i][j] = dp[i][j-1] + 1;
            }
        }
        
        
        for (int j = 0; j < col; j++){
            for (int i = 0; i < row; i++){
                if (matrix[i][j] == '0'){//think matrix[i][j] is the bottom right point of the rectangle, so if it is 0, then the area of 
                    continue;            //rectangle is 0,
                }
    
                
                int min = dp[i][j]; // dp[i][j] means the bottom edge of the rectangle
                for (int k = i; k >= 0 && matrix[i][j] == '1'; k--){//from bottom to top
                	if (min > dp[k][j]) // get the min edge from row k to i, which will consist the rectangle
                		min = dp[k][j];
                	
                	if (min * (i-k+1) > max) // calculate the area of rectangle
                		max = min * (i-k+1);
                }
                
    
       
            }
        }
        
        return max;
    }
    

    }


  • 0
    R

    "Timeout" means there is something wrong with the server.

    Relax, try again later.

    Happy Coding~


  • 0
    X

    Thanks:-). Change the subject.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.