 BiruLyu
8/2/2017 - 6:10 PM

## 85. Maximal Rectangle(#).java

``````/*
I read your solution and come up with a similar DP solution, with slightly different explanation:

Scan elements by row, calculate max distance from current element(inclusive of itself) to a top, left, right non-0 elements. Calculations from prev row can be used to calculate current row.

top(y,x) = top(y-1,x)+1 if matrix(y,x) == 1; else reset to default (0)
left(y,x) = min(left(y-1,x), max_left_distance_so_far) if matrix(y,x) == 1; else reset to default
right(y,x) = min(right(y+1,x), max_right_distance_so_far) if matrix(y,x) == 1; else reset to default
area(y,x) = (left(y,x)+right(y,x)-1)*top(y,x) if matrix(y,x) == 1
left distance should be calculated from left to right, and right distance from right to left
as we use min to calculate left & right distances, their default values should be some big enough number
since left & right distances are inclusive of current element, we should -1 when calculating width to avoid double counting
*/

public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix.length == 0) { return 0; }
int rows = matrix.length, cols = matrix.length;
int[] left = new int[cols], right = new int[cols], top = new int[cols];
Arrays.fill(left, cols); // max distance (inclusive) to left-most 1 at (y,x)
Arrays.fill(right, cols); // max distance (inclusive) to right-most 1 at (y,x)
Arrays.fill(top, 0); // max distance (inclusive) to top-most 1 at (y,x)
int max = 0;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (matrix[y][x] == '1') { top[x] += 1; }
else { top[x] = 0; }
}
int l = 0; // max left distance so far
for (int x = 0; x < cols; x++) {
if (matrix[y][x] == '1') { left[x] = Math.min(left[x], ++l); }
else { left[x] = cols; l = 0; }
}
int r = 0; // max right distance so far
for (int x = cols-1; x >= 0; x--) {
if (matrix[y][x] == '1') { right[x] = Math.min(right[x], ++r); }
else { right[x] = cols; r = 0; }
}
for (int x = 0; x < cols; x++) {
if (matrix[y][x] == '1') {
// width should exclude double count of current element
max = Math.max(max, (left[x]+right[x]-1)*top[x]);
}
}
}
return max;
}``````
``````public class Solution {
private int largestRectangleArea(int[] heights, int len) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int res = 0;
for (int i = 0; i < len; i++) {
while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
res = Math.max(res, heights[stack.pop()] * ( i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
res = Math.max(res, heights[stack.pop()] * (len - stack.peek() - 1));
}
return res;
}
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length < 1 || matrix.length < 1) return 0;
int m = matrix.length;
int n = matrix.length;
int[] heights = new int [n];
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
res = Math.max(res, largestRectangleArea(heights, n));
}
return res;
}
}``````