JAVA. please tell me what the time complexity of this solution is(I don't know how to calculate QwQ!)


  • 0
    R

    I think this code is easy to understand. Just run it then you can get it easily.QuQ

    public int maximalRectangle(char[][] matrix) {
    		if (matrix.length == 0)
    			return 0;
    		int[][] rowMtx = new int[matrix.length + 1][matrix[0].length + 1];
    		int[][] colMtx = new int[matrix.length + 1][matrix[0].length + 1];
    		for (int i = 1; i <= matrix.length; i++) {
    			for (int j = 1; j <= matrix[0].length; j++) {
    				if (matrix[i - 1][j - 1] == '1') {
    					rowMtx[i][j] = rowMtx[i][j - 1] + 1;
    					colMtx[i][j] = colMtx[i - 1][j] + 1;
    				}
    			}
    		}
    		
    		/*for (int[] i: rowMtx) {
    			for (int j: i)
    				System.out.print(j + " ");
    			System.out.println();
    		}
    		System.out.println();
    		for (int[] i: colMtx) {
    			for (int j: i)
    				System.out.print(j + " ");
    			System.out.println();
    		}
    		System.out.println();*/
    		
    		int max = 0;
    		for (int i = matrix.length; i > 0; i--) {
    			for (int j = matrix[0].length; j > 0; j--) {
    				int min = rowMtx[i][j];
    				for (int k = 0; min * colMtx[i][j] > max && k < colMtx[i][j]; k++) {
    					min = Math.min(min, rowMtx[i - k][j]);
    					max = Math.max(max, min * (k + 1));
    					//System.out.println("for => max = " + max + ", min = " + min);
    				}
    			}
    		}
    		return max;
    	}
    

Log in to reply
 

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