Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
题目要求最大的只含有1的矩形。
算法是， 计算每个点能向上连续为1的线段长度H[i][j], 这个线段能往左边拓展的位置L[i][j], 能往右边拓展的位置R[i][j]。
如图所示，对于点A来说，向上连续为1的红箭头长度为4，H[4][1] = 4。这个红箭头向左右拓展为矩形，能移动到最左边的位置L[4][1] = 1, 能移动到最右边的位置R[4][1] = 2(L包含在矩阵内，R不包含)。点A对应的矩形面积就是H * (R - L) = 4。
对于点B，H[3][2] = 3, L[3][2] = 1, R[3][2] = 4。对应的面积H * (R - L) = 9。遍历所有点，求最大的面积。因为计算是只会用一次H, L, R的数据，所以用一维数组而不是二维数组来计算。
< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHByZSBjbGFzcz0="brush:java;">public class Solution { public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int m = matrix.length; int n = matrix[0].length; int[]H = new int[n]; int[]L = new int[n]; int[]R = new int[n]; for (int i = 0; i < n; i++) { L[i] = 0; H[i] = 0; R[i] = n; } int res = 0; for (int i = 0; i < m; i++) { int left = 0; int right = n; for (int j = 0; j < n; j++) { if (matrix[i][j] == '1') { H[j]++; L[j] = Math.max(L[j], left); } else { H[j] = 0; L[j] = 0; R[j] = n; left = j + 1; } } for (int j = n - 1; j >= 0; --j) { if (matrix[i][j] == '1') { R[j] = Math.min(R[j], right); res = Math.max(res, H[j] * (R[j] - L[j])); } else { right = j; } } } return res; } }