85. Maximal Rectangle

Problem:

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Analysis:
Convert each row to histogram, then use Largest Rectangle in Histogram  approach to calc the max area. If matrix[i][j] == 0, set height to 0. If matrix[i][j] == 1, pre height + 1.

Solution:

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0)
            return 0;
        int res = 0, m = matrix.length, n = matrix[0].length;
        int[] heights = new int[n + 1];
        for (int i = 0; i < m; i++) {
            Stack<Integer> stack = new Stack<>();
            for (int j = 0; j <= n; j++) {
                if (j < n) {
                    heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
                }
                
                while (!stack.isEmpty() && heights[j] < heights[stack.peek()]) {
                    int height = heights[stack.pop()];
                    int start = stack.isEmpty() ? -1 : stack.peek();
                    res = Math.max(res, height * (j - start - 1));
                }   
                stack.push(j);  
            }
        }
        return res;
    }
        
}