这个题比刚才那个更难。

假设没做过上一个，这个简直是无情。

先想一个笨笨的解法，如何确定一个矩形呢？找一个左上角，然后每行的看能延伸到什么位置。注意随着行数的添加，列数是仅仅能变短，不能变长。

想一下也知道这样的方法的复杂度有多高。超时无疑。

假设刚好做了这个求柱形的题目。会不会收到启示呢。将矩阵中的每个1都看做是一个小的正方形。在每一列，连续的1就构成了一个柱体。求一连串这种柱体围成的最大面积就是全部1构成的最大矩形，问题被完美转化。

尽管在我看来。这种转化是非常不easy的，要不是这两个题目相邻。太难想到了。

这给了我们非常好的教训，不同的形状之间或许存在着某种联系。

置于怎么构造这种柱形就简单的多了，每一行都须要计算。看当前行当前列是1还是0，是1的话在上一行相应列的基础上长高1，是0的话直接就是0了。返回最大的面积。

class Solution {

public:

    int largestArea(int *height, int length){

        stack<int> s;

        int i=0, res=0, tpres, tph;

        while(i<length){

            if(s.empty()||height[s.top()]<=height[i]){

                s.push(i++);

            }else{

                tph = height[s.top()];

                s.pop();

                tpres = tph*(s.empty()?i:i-s.top()-1);

                res = max(res, tpres);

            }

        }

        while(!s.empty()){

            tph = height[s.top()];

            s.pop();

            tpres = tph*(s.empty()?i:i-s.top()-1);

            res = max(res, tpres);

        }

        return res;

    }

    int maximalRectangle(vector<vector<char> > &matrix) {

        int m = matrix.size();

        if(m == 0)  return 0;

        int n = matrix[0].size();

        int **h = new int*[m];

        for(int i=0;i<m;i++){

            h[i] = new int[n];

            memset(h[i], 0, sizeof(int)*n);

        }

        for(int j=0;j<n;j++){

            if(matrix[0][j] == '1'){

                ++h[0][j];

            }

        }

        for(int i=1;i<m;i++){

            for(int j=0;j<n;j++){

                if(matrix[i][j] == '1'){

                    h[i][j] = h[i-1][j]+1;

                }

            }

        }

        int res = 0;

        for(int i=0;i<m;i++){

            res = max(res, largestArea(h[i], n));

            delete [] h[i];

        }

        delete [] h;

        return res;

    }

};