[LeetCode]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.

動態規劃

用left[ ]數組紀錄該點距離最左邊（在矩形內部）的1的距離，用right[ ]數組紀錄該點距離最右邊（在矩形內部）的1距離，height[ ]記錄該點的矩形內1的最大高度

public class Solution {
	public int maximalRectangle(char[][] matrix) {
		if (matrix.length == 0)	return 0;
		int row = matrix.length;
		int column = matrix[0].length;
		int left[] = new int[column], right[] = new int[column], height[] = new int[column];
		Arrays.fill(right, column-1);
		int res = 0;
		for (int i = 0; i < row; i++) {
			int l = 0, r = column - 1;
			for (int j = 0; j < column; j++) {
				if (matrix[i][j] == '1') {
					left[j] = Math.max(left[j], l);
					height[j]++;
				} else {
					l = j+1;
					left[j] =0;
					height[j] = 0;
					right[j] = column - 1;
				}
			}

			for (int j = column - 1; j >= 0; j--) {
				if (matrix[i][j] == '1') {
					right[j] = Math.min(r, right[j]);
					res = Math.max(res, height[j] * (right[j] - left[j]+1));
				} else {
					r = j-1;
				}
			}
		}
		return res;
	}
}