Java short dp solution, beats 75%. 2 lines commented code matters the run time!


  • 0
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0||matrix[0].length==0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int maxres = 0;
        int[][] mostleft = new int[m][n];
        int[][] mosttop = new int[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(matrix[i][j]=='1'){
                    if(i>0) mosttop[i][j] = mosttop[i-1][j]+1;
                    else mosttop[i][j] = 1;
                    if(j>0) mostleft[i][j] = mostleft[i][j-1]+1;
                    else mostleft[i][j] = 1;
                }
            }
        }
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
                if((i+1)*(j+1)<=maxres) break;//cannot find a bigger rectangle.
                if(matrix[i][j]=='1'){
                    int leftlen = mostleft[i][j];
                    int currmax = 0;
                    int minheight = m;
                    for(int wid = 0;wid<leftlen;wid++){
                        int currheight = mosttop[i][j-wid];
                        minheight = minheight>currheight?currheight:minheight;
                        if(minheight*leftlen<maxres) break;//Another line to make the loop end faster.
                        int currsize = minheight*(wid+1);
                        currmax = currmax>currsize?currmax:currsize;
                    }
                    if(currmax>maxres) maxres = currmax;
                }
            }
        }
        return maxres;
    }

Log in to reply
 

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