leetcode 85. Maximal Rectangle(最大全1子矩阵)

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

这道题有好多方法，DP法，直方图法。由于我急着做算法作业，所以就只理解并写了DP法，至于其他方法，等有空再慢慢看。先把链接放这哈：https://leetcode.com/problems/maximal-rectangle/description/

使用了三个数组，left[], right[], height[]，注意它们的长度都是 n，也就是列的长度。

height 代表 当前点往上连续的 1 的个数(要加上当前的1). 而 left & right 则是 包含当前点的且高度为 height的矩形的左边界和右边界。

DP方法是从第一行开始，一行一行地执行。包含 (i,j) 点的矩形的面积这样计算：[right(i,j) - left(i,j) + 1] * height(i,j).

其中每一行的left, right, and height 都能使用上一行的和这一行的信息来算出，所以这是一个DP的方法。转化公式为：

left(i,j) = Max[ left(i-1,j), cur_left ] , cur_left can be determined from the current row

right(i,j) = Min[ right(i-1,j), cur_right ], cur_right can be determined from the current row

height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';

height(i,j) = 0, if matrix[i][j]=='0'

这是一个方便理解的例子：

example:

0 0 0 1 0 0 0 
0 0 1 1 1 0 0 
0 1 1 1 1 1 0

The vector "left" , "right" and "height" from row 0 to row 2 are as follows

row 0:

l: 0 0 0 3 0 0 0
r: 7 7 7 4 7 7 7h: 0 0 0 1 0 0 0

row 1:

l: 0 0 2 3 2 0 0
r: 7 7 5 4 5 7 7 
h: 0 0 1 2 1 0 0 

row 2:

l: 0 1 2 3 2 1 0
r: 7 6 5 4 5 6 7
h: 0 1 2 3 2 1 0

下面是代码：

package leetcode;

public class Maximal_Rectangle_85 {

	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[] height = new int[n];
		int[] left = new int[n];
		int[] right = new int[n];
		for (int i = 0; i < n; i++) {
			right[i] = n - 1;
		}
		int max_area = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1') {
					height[j] = height[j] + 1;
				} else {
					height[j] = 0;
				}
			}
			int current_left = 0;
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1') {
					left[j] = Math.max(left[j], current_left);
				} else {
					left[j] = 0;
					current_left = j + 1;
				}
			}
			int current_right = n - 1;
			for (int j = n - 1; j >= 0; j--) {
				if (matrix[i][j] == '1') {
					right[j] = Math.min(right[j], current_right);
				} else {
					right[j] = n - 1;
					current_right = j - 1;
				}
			}
			for(int j=0;j<n;j++){
				int area=(right[j]-left[j]+1)*height[j];
				max_area=Math.max(max_area, area);
			}
		}
		return max_area;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Maximal_Rectangle_85 m=new Maximal_Rectangle_85();
		char[][] matrix=new char[][]{
			{'1','0','1','0','0'},
			{'1','0','1','1','1'},
			{'1','1','1','1','1'},
			{'1','0','0','1','0'}
		};
		System.out.println(m.maximalRectangle(matrix));
	}

}

等有空再来补充直方图法。