package leetcode.array;

/**

* @ClassName MaximalRectangle

* @Description 最大矩形 https://leetcode-cn.com/problems/maximal-rectangle/

* @Author changxuan

* @Date 2020/12/26 下午8:40

**/

public class MaximalRectangle {

public int maximalRectangle(char[][] matrix) {

int m = matrix.length;

if (m == 0) {

return 0;

}

int n = matrix[0].length;

int[][] left = new int[m][n];

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (matrix[i][j] == '1') {

left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;

}

}

}

int ret = 0;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (matrix[i][j] == '0') {

continue;

}

int width = left[i][j];

int area = width;

for (int k = i - 1; k >= 0; k--) {

width = Math.min(width, left[k][j]);

area = Math.max(area, (i - k + 1) * width);

}

ret = Math.max(ret, area);

}

}

return ret;

}

}