Maximal Rectangle

MaximalRectangle.java

/**
 * Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
 */
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        int n = m == 0 ? 0 : matrix[0].length;
        int[][] height = new int[m][n];
        int maxArea = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '0')
                    height[i][j] = 0;
                else
                    height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1;
            }
        }
        for(int i = 0; i < m; i++) {
            // row by row
            int area = maxAreaInHist(height[i]);
            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    }
    private int maxAreaInHist(int[] height) {
        Stack<Integer> s = new Stack<Integer>();
        int i = 0;
        int maxArea = 0;
        while(i < height.length) {
            if(s.isEmpty() || height[s.peek()] <= height[i])
                s.push(i++);
            else {
                int top = s.pop();
                maxArea = Math.max(maxArea, height[top] * (s.isEmpty() ? i : i - s.peek() - 1));
            }
        }
        while(!s.isEmpty()) {
            int top = s.pop();
            maxArea = Math.max(maxArea, height[top] * (s.isEmpty() ? i : i - s.peek() - 1));
        }
        return maxArea;
    }
}