Concise Java solution in 20 lines.


  • 0
    A

    For each consider the rectangles with bottoms in that line. Use one stack as in the histogram problem.

    public class Solution {
        public int maximalRectangle(char[][] matrix) {
            if (matrix == null || matrix.length == 0|| matrix[0].length == 0) return 0;
            int m = matrix.length, n = matrix[0].length;
            int area = 0;
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            int[] a = new int[n+1];
            a[n] = -m-1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n+1; j++) {
                    a[j] = (j == n || matrix[i][j] == '1')? a[j] + 1 : 0;    //Update the height of the rectangle
                    while (stack.peek() >= 0 && a[stack.peek()] > a[j]) {
                        area = Math.max(area, a[stack.pop()]*(j-1 - stack.peek()));
                    }
                    stack.push(j%n - j/n);  // This is to make sure if j == n, we push -1.
                }
            }
            return area;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.