# Maximal Rectangle

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

Example:

```Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6```
Solution:

class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if (m == 0) return 0;
int n = matrix[0].length;
if (n == 0) return 0;
int[][] M = new int[m][n];
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
M[i][j] = matrix[i][j] - '0';
}
}
for (int i = 1; i < m; i ++) {
for (int j = 0; j < n; j ++) {
M[i][j] = M[i][j] == 0 ? 0 : 1 + M[i - 1][j];
}
}
int max = 0;
for (int i = 0; i < m; i ++) {
max = Math.max(max, maxHistogram(M[i]));
}
return max;
}

// 3 1 3 2 2
private int maxHistogram(int[] arr) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
int max = 0;
for (int i = 1; i <= arr.length; i ++) {
int cur = i == arr.length ? -1 : arr[i];
if (stack.isEmpty() || cur >= arr[stack.peekFirst()]) {
stack.push(i);
} else {
while (!stack.isEmpty() && cur < arr[stack.peekFirst()]) {
int height = arr[stack.pop()];
int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
max = Math.max(max, height * (i - left));
}
stack.push(i);
}
}
return max;
}
}