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.
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 = []
**Output:** 0
Example 3:
**Input:** matrix = [["0"]]
**Output:** 0
Example 4:
**Input:** matrix = [["1"]]
**Output:** 1
Example 5:
**Input:** matrix = [["0","0"]]
**Output:** 0
Constraints:
rows == matrix.length
cols == matrix[i].length
0 <= row, cols <= 200
matrix[i][j] is '0' or '1'.
ac1: Stack
similar with #84
class Solution {
public int maximalRectangle(char[][] matrix) {
// edge cases
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int max = 0;
int row = matrix.length, col = matrix[0].length;
int[] h = new int[col];
// iterate row
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
h[c] = matrix[r][c] == '1' ? h[c] + 1 : 0;
}
max = Math.max(max, maxArea(h)); // O(n)
}
return max;
}
private int maxArea(int[] h) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);
int max = 0;
for (int i = 0; i <= h.length; i++) {
int currh = i == h.length ? 0 : h[i];
while (stack.peek() != -1 && currh < h[stack.peek()]) {
max = Math.max(max, h[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
return max;
}
}
/*
stack, similar with #84
row by row: int[] h = new int[matrix[0].length]
if [i] == 1, h[i] = h[i] + 1, otherwise h[i] = 0
calculate max area like #84
*/
