Maximal Rectangle !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

A:
简单的seading算法，（就是假装某点为左上角的corner，然后grow） 应该是太慢了。要注意利用rectangle这个词儿。------------O(n^3)

哎，学会了就行了。 那么纠结干啥？
你就是费劲巴力自己做出来， 有个屁用啊？Tiger， 你SB
这道题，是自己直接上网搜的思路。  看这里, 和这里
具体就是：利用求histogram的思路， 一层层地求最大面积。

 build a cache to make this problem to a list of "Largest Rectangle in Histogram" in M layers 
will take O(M*N^2) time and O(M) space

--------------------第二遍------------------

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int m = matrix.length, n = matrix[0].length,maxArea = 0;
        int[] hist = new int[n];
        for (int i = 0; i < m; i++) { // for each row
            for (int j = 0; j < n; j++)
                hist[j] = matrix[i][j] == '0'? 0: hist[j]+1 ;
            maxArea = Math.max(maxArea, getMaxArea(hist));
        }
        return maxArea;
    }
    public int getMaxArea(int[] hist) { // calculate the max-area of a histogram
        int maxArea = 0, n = hist.length;
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            int preIndex = i;
            while( ! stack.isEmpty()){
                int[] tmp = stack.peek();
                if( hist[i] < tmp[1]  ){ // calculate area before i
                    stack.pop();
                    maxArea = Math.max(maxArea, tmp[1] * (i-tmp[0]));
                    preIndex = tmp[0];
                }else{
                    break;
                }
            }
            stack.push( new int[]{preIndex,hist[i]} );
        }
        while( ! stack.isEmpty() ){
            int[] tmp = stack.pop();
            maxArea = Math.max(maxArea, tmp[1] * (n-tmp[0]) );
        }
        return maxArea;
    }
}

Mistakes:
这里的核心还是利用histgram 求矩形面积。
其难点在2个地方：
1： 每次发现一个更高的， 则push stack。 否则，计算其前面的比他小的矩形的面积（不包括现在的位置）    2：  计算完毕，重新push的时候，需要存入 最远的index，和现在的高度。（因此我们需要记录 preIndex)  


Learned:
1： 用极大化思想解决最大子矩形问题