085 - Maximal Rectangle

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.
Hide Tags
Array Hash Table Stack Dynamic Programming
Hide Similar Problems
(H) Largest Rectangle in Histogram (M) Maximal Square

做得比较折腾的一道题，一开始觉得是个烂题，就是麻烦，全部弄完了回头再看，是个好题。
总共做了DP，数组，stack三种解法，耗时分别是TLE, 68 ms/12 ms，20 ms。

一开始上来觉得是DP，提示里确实也有，于是就折腾状态方程，一维的buffer是不够的，那就二维吧。
可是怎么折腾发现在二维里都不可能整理出统一的状态方程来，画了各种case越画越乱，
后来想到，应该是遇到一个0，就递归进去，对这个0的右边和下边再次做DP，每次返回DP里最大的，
这样所有层次的DP都完成之后，就可以找到最大的了。画了几个矩阵试了试，可行。
可是代码跑上去出问题了，递归的时候，想着不要落下最大可能的范围，所以新范围的起点选的是 0, y 或者 x, 0，
这样在遇到一些case，有整列0的时候，就会来回递归，死循环！试着加了一些保护条件，无果。
仔细画图分析，因为怕遗漏，总是从0开始，这样就算不死循环，也是大量重复···
不如把起点改成 rstart, y 或 x, cstart，一来少一些重复，而来应该可以避免死循环~，果然，不再死循环了！
虽然这个递归 DP 的solution是可以work的，但是耗时也是巨大无比的。。。

显然递归 DP 不可行，单遍DP的方程还是没弄出来，只好跑去看帖子。。，果然看到一个颇为精彩的思路：
把每一行都当做一个直方图，0就是0，1就继承上一行的值，这样题目就演化成了前一题Largest Rectangle in Histogram！
难怪这两道题是挨在一起的。。！果真是没想到啊···
于是就按照这个思路重新写，发现用之前一题的数组回头跑出来居然要68 ms？！换了用stack的方法，是20 ms！
不理解。。。，回过头去重新琢磨前一题，比较两个方法的操作过程，
擦，用栈只要向前找到比峰值下一个值小的，就不再比较了，但我那用数组的，每次都比到头，难怪耗时多！！
按照栈的做法改进了一下，多push一个0，然后比到更小的就不比了，验证通过之后，把它再拿过来，果然，12 ms妥妥地！！

还是思路狭窄啊！！一来没联系起前一道题，二来就算是单就前一道题，数组的解法也仍然有优化的余地但没想到。赶紧更新前一道题的帖子，也记录在这道题里头，以后遇题要在多想想！！

另外还是好奇DP的解法，先mark一下，回头找个时间再看看。
已经看到了，相当精妙的 DP 解法！！

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rst = 0;
        int sz = matrix.size();
        if(sz)
        {
            int zz=matrix[0].size();
            if(zz)
            {
                for(int ii=0; ii<sz; ++ii)
                {
                    //build Histogram for each line
                    for(int jj=0; jj<zz; ++jj)
                        matrix[ii][jj] = ('1'==matrix[ii][jj])? ((ii)? (matrix[ii-1][jj] + 1):1) : 0;
                    //then call method in "084 - Largest Rectangle in Histogram"
                    //to get max rectangle in this line.
                    rst = max(rst, largestRectangleArea1(matrix[ii]));
                }
            }
        }
        return rst;
    }
    //import from Share my DP solution, go back in array
    int largestRectangleArea1(vector<char>& height) {
        int rst=0;
        int sz = height.size();
        if(sz)
        {
            height.push_back(0);            //##> idea from solution of stack
            sz++;                           //##> idea from solution of stack
            int begin=0, idx1=0;
            for( ; idx1<sz; ++idx1)
            {
                //find next peak
                while(idx1<sz-1 && height[idx1+1]>=height[idx1])
                    idx1++;
               
                //get max area before this peak
                int low=height[idx1];
                int next=height[idx1+1];    //##> idea from solution of stack
                rst = max(low, rst);
                for(int ii=idx1-1;
                        ii>=0,              /*don't use 'begin'*/
                        height[ii]>next;    //##> idea from solution of stack
                        ii--)
                {
                    low = min((int)height[ii], low);
                    rst = max(low*(idx1-ii+1), rst);
                }
                //begin = idx1
            }
        }
        return rst;
    }
    //import from Share my DP solution, go back with stack
    int largestRectangleArea2(vector<char> &height) {
        int res = 0;
        stack<int> s;
        height.push_back(0);
        for (int i = 0; i < height.size(); ++i) {
            if (s.empty() || height[s.top()] <= height[i]) s.push(i);
            else {
                int tmp = s.top();
                s.pop();
                res = max(res, height[tmp] * (s.empty() ? i : (i - s.top() - 1)));
                --i;
            }
        }
        return res;
    }
  
    //---------------------------- solution Time Limit Exceeded ----------------------------
    int maximalRectangle_timeout(vector<vector<char>>& matrix) {
        int rst = 0;
        int sz = matrix.size();
        if(sz)
        {
            int zz=matrix[0].size();
            if(zz)
                rst = find(matrix, 0, 0, sz-1, zz-1);
        }
        return rst;
    }
   
    int find(vector<vector<char>>& matrix, int rstart, int cstart, int rend, int cend)
    {
        int rst = 0, sz = rend-rstart+2, zz=cend-cstart+2;
        vector<vector<int>> buf(sz, vector<int>(zz, 0));        for(int ii=1; ii<sz; ++ii)
        {
            for(int jj=1; jj<zz; ++jj)
            {
                int im=ii-1+rstart, jm=jj-1+cstart;
                char cm = matrix[im][jm];
                int upon = buf[ii-1][jj], left = buf[ii][jj-1], diag = buf[ii-1][jj-1];
                if('0'==cm)
                {
                    //recursive call for right, bottom, right-bottom rectangle.
                    //right
                    if(jj+cstart<=cend)
                        rst = max(rst, find(matrix, rstart, jj+cstart, rend, cend));
                    //bottom
                    if(ii+rstart<=rend)
                        rst = max(rst, find(matrix, ii+rstart, cstart, rend, cend));
                    return rst;
                }
                else    //if('1'==cm)
                {
                    buf[ii][jj] = upon + left + (1 - diag);
                    rst = max(rst, buf[ii][jj]);
                }
            }
        }
        return rst;
    }
};
68 ms/12 ms, 20 ms, TLE.