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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

一刷
題解：
解題思路

根據(jù)上圖，可以清楚的看出本題可以轉(zhuǎn)化為Largest Rectangle in Histogarm來做
初始化height = [0, 0 ,0 ....]
對于每一行，先求出以這一行為x軸的每個柱子的高度，求解時(shí)，可以每次基于上一行的值進(jìn)行更新。然后O(n)的時(shí)間求出最大矩形，不斷更新全局變量res
時(shí)間復(fù)雜度為 O(n * (n + n)) = O(n2)

public class Solution {
    public int maximalRectangle(char[][] matrix) {
       if(matrix == null || matrix.length == 0) return 0;
       
       int colNum = matrix[0].length;
       int[] accumulatedHeights = new int[colNum];
       int max = 0;
       for(char[] row : matrix){
           for(int i=0; i<colNum; i++){
               //the accumulated, consecutive number of 1
                accumulatedHeights[i] = row[i] == '0' ? 0 : accumulatedHeights[i] + 1;
           }
           max = Math.max(calcLargestHist(accumulatedHeights), max);
       }
       return max;
    }
    
    private int calcLargestHist(int[] heights){
         if(heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<Integer>();//store the index
        int max = 0;
        for(int i=0; i<=heights.length; i++){
            int curt = (i == heights.length)? -1: heights[i];//guaranteen the stack is ascending
            while(!stack.isEmpty() && curt<=heights[stack.peek()]){
                int h = heights[stack.pop()];
                int w = stack.isEmpty()? i: i - stack.peek() - 1;
                max = Math.max(max, h*w);
            }
            stack.push(i);
        }
        
        return max;
    }
}