Cacher is the code snippet organizer for pro developers

/*
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[0].length == 0) { return 0; }
	int rows = matrix.length, cols = matrix[0].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[0].length < 1) return 0;
        int m = matrix.length;
        int n = matrix[0].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;
    }
}