Leetcode 85 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.

Solution 1: translate this problem to max rectangular in histogram. Calculate max histogram in each row. Details below:

 public class Solution {  
   public int maximalRectangle(char[][] matrix) {  
     int m=matrix.length;  
     if (m==0) return 0;  
     int n=matrix[0].length;  
     int[][] his=new int[m][n];  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (i==0) his[i][j]=matrix[i][j]=='0'?0:1;  
         else his[i][j]=matrix[i][j]=='0'?0:1+his[i-1][j];  
       }  
     }  
     int res=0;  
     for (int i=0; i<m; i++) res=Math.max(res,calHis(his[i]));  
     return res;  
   }  
   private int calHis(int[] nums) {  
     int n=nums.length, res=0;  
     Deque<Integer> stack=new LinkedList<>();  
     for (int i=0; i<n; i++) {  
       while (!stack.isEmpty() && nums[stack.peek()]>nums[i]) {  
         int j=stack.pop();  
         int left=stack.isEmpty()?0:stack.peek()+1;  
         res=Math.max(res,nums[j]*(i-left));  
       }  
       stack.push(i);  
     }  
     while (!stack.isEmpty()) {  
       int j=stack.pop();  
       int left=stack.isEmpty()?0:stack.peek()+1;  
       res=Math.max(res,nums[j]*(n-left));  
     }  
     return res;  
   }  
 }