Maximal Rectangle

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

Solution1:
Calculate area starts from its bottom-right corner.

///// calculate rectangle area from its right-bottom corner /////

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(m == 0) return 0;
        int n = matrix[0].length;
        
        int[][] num = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '0'){ 
                    num[i][j] = 0;
                }
                else{
                    // the number of consective ones on the same row
                    num[i][j] = j == 0 ? 1 : num[i][j-1] + 1;   
                }
            }
        }
        
        int max = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // "build up" all possible rectangles from this point
                if(num[i][j] != 0){
                    // one row
                    max = Math.max(max, num[i][j]);
                    int min_width = num[i][j];
                    
                    // try to add up more rows above into rectangle 
                    int h = i - 1;
                    while(h >= 0 && num[h][j] != 0){
                        min_width = Math.min(min_width, num[h][j]);
                        max = Math.max(max, min_width * (i-h+1));
                        h--;
                    }
                }
            }
        }
        return max;
    }
}

Solution2:
We can change this question to rectangle histogram question.
for each row, get a rectangle histogram

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if(n == 0) return 0;
        int m = matrix[0].length;
        int[][] num = new int[n][m];
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                num[i][j] = matrix[i][j] - '0';           
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                if(num[i][j] == 1) num[i][j] += num[i-1][j];           
            }
        }
        int maxArea = 0;
        for(int i = 0; i < n; i++){
            maxArea = Math.max(maxArea, helper(num[i]));
        }
        return maxArea;
    }
    // largest rectangle in histogram
    public int helper(int[] height){
        Stack stack = new Stack();
        int[] h = new int[height.length + 1];
        h = Arrays.copyOf(height, height.length + 1);
        int i = 0;
        int maxArea = 0;
        while(i < h.length){
            if(stack.isEmpty() || h[i] >= h[stack.peek()]){
                stack.push(i++);
            }
            else{
                int t = stack.pop();
                if(stack.isEmpty()){
                    maxArea = Math.max(maxArea, h[t] * i);
                }
                else{
                    maxArea = Math.max(maxArea, h[t] * (i - 1 - stack.peek()));
                }
            }
        }
        return maxArea;
    }
}