求全是1的最大矩阵面积 Maximal Rectangle @LeetCode

一开始参考http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/，但发现它的条件是square submatrix，所以本题不符合。

后来参考http://yucoding.blogspot.com/2013/01/incomplete-leetcode-question-47-maximal.html写的很详细了，转抄于此：

Analysis:

This is not an easy problem and the idea is not straightforward.
Since the question requires the area of all ones region, first we can define the region (rectangle) in the matrix. Any region in the matrix has several basic properties: 1 corner point, width, and length.
Also which corner point it is decide the exact place of the region, here we consider the bottom-right corner point, because we usually scan the matrix from (0,0) to right and down direction. For this problem, we also need to consider the "all ones" requirement, where all the regions are filled with 1s.

We can then have this data structure:
One 2D array(vector) ones[i][j], where ones[i][j] stores the number of contiguous 1s ended at matrix[i][j], along ith row. e.g. if matrix[i] = "1011101", then ones[i]=1,0,1,2,3,0,1. This array stores the length of the rectangle, for every possible bottom-right corner point.

Having this two values, next is to find the height of the rectangle, as well as keep the "all ones" requirement.
Start with a corner point [i][j], since it is the bottom right corner, the rectangle search direction is left and up.
For the left we already have the number of contiguous 1s ones[i][j]. How to get the height? We need to scan all the values above ones[i][j], it is from i-1 to 0. If meets 0, then stop, else compute the possible rectangle area, and store the max. To compute the area, the minimum length of rectangle should be compared and stores every time.

package Level5;

/**
 * Maximal Rectangle 
 * 
 * Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
 *
 */
public class S85 {

	public static void main(String[] args) {
		char[][] matrix = {{'0','1'},{'0','1'}};
		System.out.println(maximalRectangle(matrix));
	}
	
	public static int maximalRectangle(char[][] matrix) {
		int rows = matrix.length;
		if(rows == 0){
			return 0;
		}
		int cols = matrix[0].length;
		// 先计算全1矩阵的宽度
        int[][] hOnes = new int[rows][cols];		// horizontal ones
        
        int max = 0;	// 最大面积
        for(int i=0; i<rows; i++){
        	for(int j=0; j<cols; j++){
        		if(matrix[i][j] == '1'){
        			if(j == 0){	// 特殊处理左起第一个
        				hOnes[i][j] = 1;
        			}else{
        				hOnes[i][j] = hOnes[i][j-1] + 1;
        			}
        		}
        	}
        }
        
        for(int i=0; i<rows; i++){
        	for(int j=0; j<cols; j++){
        		if(hOnes[i][j] != 0){
        			int minI = i;	// 计算高度，minI不断向上走
        			int minRowWidth = hOnes[i][j];	// 随着向上走，宽度也要随之调整
        			while(minI >= 0){
        				minRowWidth = Math.min(minRowWidth, hOnes[minI][j]);
        				int area = minRowWidth * (i-minI+1);
        				max = Math.max(max, area);
        				minI--;
        			}
        		}
        	}
        }
        
        return max;
    }

}