My solution on Java using DP


  • 9
    Y

    Open matrix from top to the bottom line by line, counting height of each column. Then check for each column (only if it wasn't counted already) how many times it appears to the right and to the left. Area = (left+right)*height. Just pick the max one. Pretty fast

    public class Solution {
        public int maximalRectangle(char[][] matrix) {
            int area = 0, new_area, r, l;
            if(matrix.length > 0){
                int[] line = new int[matrix[0].length];
                boolean[] is_processed = new boolean[matrix[0].length];
                for(int i = 0; i < matrix.length; i++){
                    for(int j = 0; j < matrix[i].length; j++){
                        if (matrix[i][j] == '1') {
                            line[j]++;
                            is_processed[j] = false;
                        } else {
                            line[j] = 0;
                            is_processed[j] = true;
                        }
                    }
                    for(int j = 0; j < matrix[i].length; j++){
                        if(is_processed[j]) continue;
                        r = l = 1;
                        while((j + r < line.length)&&(line[j + r] >= line[j])){
                            if(line[j + r] == line[j]) is_processed[j + r] = true;
                            r++;
                        }
                        while((j - l >= 0)&&(line[j - l] >= line[j])) l++;
                        new_area = (r + l - 1)*line[j];
                        if (new_area > area) area = new_area;
                    }
                }
            } return area;
        }
    }

  • 0
    L

    Seems that the time complexity is O(n^3) ?


  • 0
    Z

    @liji94188 nope I don't think so


  • 0
    C
    This post is deleted!

  • 0
    T

    why it is O(n^2), I think it should be O(n^3)? For exmple, if I have 1,2,3,4,5,6...100, I think the worst case should be O(n^3)


  • 0
    Z

    @tiandiao123 it will be a n times outer loop with m times inner loop if data is M[n][m]. hence time is O(n*m)


Log in to reply
 

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