# 85. Maximal Rectangle

Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

## Ex

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.


Example 2:

Input: matrix = [["0"]]
Output: 0


Example 3:

Input: matrix = [["1"]]
Output: 1


## Constraints:

rows == matrix.length

cols == matrix[i].length

1 <= row, cols <= 200

matrix[i][j] is ‘0’ or ‘1’.

# V1-暴力算法

## 思路

m[i][j]  x x x
x
x
x


1) 如果 m[i][j] == 0，直接跳过。

2) 如果不是，则向右向下，一直到矩阵的最右下角，构成一个矩形。判断这个矩形是不是全部是1

3）如果全部是1，则更新计算 maxArea 的值。

## java

public class T085_MaximalRectangle {

private boolean isAllOnes(char[][] matrix,
int xStart,
int xEnd,
int yStart,
int yEnd) {
for(int x = xStart; x <= xEnd; x++) {
for(int y = yStart; y <= yEnd; y++) {
if(matrix[x][y] == '0') {
return false;
}
}
}

return true;
}

/**
* 最大的长方形
* @param matrix 矩阵
* @return
*/
public int maximalRectangle(char[][] matrix) {
int maxArea = 0;

// 行
int rowSize = matrix.length;
// 列
int columnSize = matrix[0].length;

// 直接遍历整个矩阵
for(int i = 0; i < rowSize; i++) {
for(int j = 0; j < columnSize; j++) {
// 当前位置为0，则跳过
if(matrix[i][j] == '0') {
continue;
}

// 从当前位置开始，向右向下遍历。
for(int x = i; x < rowSize; x++) {
for(int y = j; y < columnSize; y++) {
// 跳过为0的元素
if(matrix[x][y] == '0') {
continue;
}

// 判断从 横介于[i,x]，纵介于[j,y]的矩阵。
// 如果这个矩阵都是1，则计算更新对应的 area。
if(isAllOnes(matrix, i, x, j, y)) {
int area = (x-i+1) * (y-j + 1) ;
maxArea = Math.max(maxArea, area);
}
}
}
}
}

return maxArea;
}

}


# V2-初步优化

## 思路

boolean[][] isAllOneCache = new boolean[][];


boolean isOneFlag = matrix[p][q]=='1';

// 左边的结果 & 当前
if(p>i) dp[p][q] = isOneFlag & dp[p-1][q];

// 上边的结果 & 当前
if(q>j) dp[p][q] = isOneFlag & dp[p][q-1];


## 实现

public class T085_MaximalRectangleV2 {

/**
* 最大的长方形
*
* 优化思路：缓存对于是否全部为 1 的判断
* @param matrix 矩阵
* @return
*/
public int maximalRectangle(char[][] matrix) {
int maxArea = 0;

// 行
int rowSize = matrix.length;
// 列
int columnSize = matrix[0].length;

// 直接遍历整个矩阵
for(int i = 0; i < rowSize; i++) {
for(int j = 0; j < columnSize; j++) {
// 当前位置为0，则跳过
if(matrix[i][j] == '0') {
continue;
}

// 是否都为1的缓存
boolean[][] allOneDp = new boolean[rowSize][columnSize];

// 从当前位置开始，向右向下遍历。
for(int x = i; x < rowSize; x++) {
for(int y = j; y < columnSize; y++) {
allOneDp[x][y] = matrix[x][y] == '1';

// 复用以前的
if(x > i) {
allOneDp[x][y] = allOneDp[x][y] & allOneDp[x-1][y];
}
if(y > j) {
allOneDp[x][y] = allOneDp[x][y] & allOneDp[x][y-1];
}

// 如果满足，则计算更新
if(allOneDp[x][y]) {
maxArea = Math.max(maxArea, (x-i+1)*(y-j+1));
}
}
}
}
}

return maxArea;
}

}


# V3-O(n^2)

## 思路

1 1 0 1 0 1

0 1 0 0 1 1

1 1 1 1 0 1

1 1 1 1 0 1


## 实现

    public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}

int[] height = new int[matrix[0].length];
for (int i = 0; i < matrix[0].length; i++) {
if (matrix[0][i] == '1') {
height[i] = 1;
}
}
int result = largestInLine(height);
for (int i = 1; i < matrix.length; i++) {
resetHeight(matrix, height, i);
result = Math.max(result, largestInLine(height));
}

return result;
}

private void resetHeight(char[][] matrix, int[] height, int idx) {
for (int i = 0; i < matrix[0].length; i++) {
if (matrix[idx][i] == '1') {
height[i] += 1;
} else {
height[i] = 0;
}
}
}

public int largestInLine(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int len = height.length;
Stack<Integer> s = new Stack<>();
int maxArea = 0;
for (int i = 0; i <= len; i++) {
int h = (i == len ? 0 : height[i]);
if (s.isEmpty() || h >= height[s.peek()]) {
s.push(i);
} else {
int tp = s.pop();
maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
i--;
}
}
return maxArea;
}


# 参考资料

https://leetcode.com/problems/maximal-rectangle/solutions/29055/my-java-solution-based-on-maximum-rectangle-in-histogram-with-explanation/

https://leetcode.com/problems/maximal-rectangle/solutions/29054/share-my-dp-solution/

https://leetcode.com/problems/maximal-rectangle/solutions/29094/evolve-from-brute-force-to-optimal/

https://leetcode.com/problems/maximal-rectangle/