Maximal Rectangle

Version #1 (LintCode) DP
Time O(#rows * #cols)
Space O(#cols)
public class Solution {
    /**
     * @param matrix a boolean 2D matrix
     * @return an integer
     */
    public int maximalRectangle(boolean[][] matrix) {
        // Write your code here
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        int maxRec = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] height = new int[cols];
        //left & right are exclusive
        int[] left = new int[cols];
        int[] right = new int[cols];
        Arrays.fill(left, -1);
        Arrays.fill(right, cols);
        int currLeft, currRight;
        int y;
        for (int x = 0; x < rows; x++) {
            currLeft = -1;
            currRight = cols;
            for (y = 0; y < cols; y++) {
                if (matrix[x][y]) {
                    height[y]++;
                    left[y] = Math.max(left[y], currLeft);
                 
                } else {
                    height[y] = 0;
                    left[y] = -1;
                    currLeft = y;
                }
            }
            for (y = cols - 1; y >= 0; y--) {
                if (matrix[x][y]) {
                    right[y] = Math.min(right[y], currRight);
                    maxRec = Math.max(maxRec, (right[y] - left[y] - 1) * height[y]);
                } else {
                    right[y] = cols;
                    currRight = y;
                }
            }
        }
        return maxRec;
    }
}

Version #2 Stack (LeetCode)

可以简化。。。对column 1 pass 下次刷的时候重新写一下

Time O(#rows * #cols)
Space O(#cols) consider the garbage collection
51.85% 
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] height = new int[cols];
     
        int maxRec = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') height[col]++;
                else height[col] = 0;
            }
            maxRec = Math.max(maxRec, histgramMax(height));
        }
        return maxRec;
    }
 
    private int histgramMax(int[] histgram) {
        //stack of indicies
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        int curr, left, right;
        for (right = 0; right < histgram.length; right++) {
            while (!stack.isEmpty() && histgram[right] < histgram[stack.peek()]) {
                curr = stack.pop();
                left = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, histgram[curr] * (right - left - 1));
            }
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            curr = stack.pop();
            left = stack.isEmpty() ? -1 : stack.peek();
            right = histgram.length;
            max = Math.max(max, histgram[curr] * (right - left - 1));
        }
        return max;
    }
 
}