【Maximal Rectangle】cpp

题目：

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

代码：

class Solution {

public:

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

        {

            if (matrix.empty()) return ;

            const int ROW = matrix.size();

            const int COL = matrix[].size();

            vector<int> height(COL,);

            vector<int> l_most(COL,);

            vector<int> r_most(COL,COL-);

            int max_area = ;

            for ( int i = ; i < ROW; ++i )

            {

                int l_curr = ;

                int r_curr = COL-;

                // calculate current row's height

                for ( int j = ; j < COL; ++j )

                {

                    height[j] = matrix[i][j]=='' ? height[j]+ : ;

                }

                // from left to right

                for ( int j = ; j < COL; ++j )

                {

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

                    {

                        l_most[j] = std::max(l_most[j], l_curr);

                    }

                    else

                    {

                        l_most[j] = ;

                        l_curr = j+;

                    }

                }

                // from right to left

                for ( int j = COL-; j>=; --j )

                {

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

                    {

                        r_most[j] = std::min(r_most[j], r_curr);

                    }

                    else

                    {

                        r_most[j] = COL-;

                        r_curr = j-;

                    }

                }

                // calculate area of rectangle

                for ( int j = ; j<COL; ++j )

                {

                    max_area = std::max(max_area, (r_most[j]-l_most[j]+)*height[j]);

                }

            }

            return max_area;

        }

};

tips：

学习了网上的O(m×n)时间复杂度的解法。

这道题的路子类似于http://www.cnblogs.com/xbf9xbf/p/4499450.html

总体的思路如下：

每次遍历一行的元素，以这一行作为X轴；模仿largest rectangle in histogram这道题

大体思路如下，需要对largest rectangle in histogram这道题有比较深刻的理解

a) 计算每个点的当前高度

b) 计算当前高度下每个点能往左推到哪个位置

c) 计算当前高度下每个点能往右推到哪个位置

d) 遍历以当前行作为X轴可能获得的最大面积

a)~d)走完所有行，就可以获得最大的矩形面积

思路实在精妙，详细记录下思考每个环节的过程：

a) 如何计算当前点的高度？

利用滚动数组技巧：height[j]记录的是到i-1行该列对应的高度；如果matrix[i][j]=='1'，则height[j] += 1，即比上一行该列位置+1；如果matrix[i][j]=='0'则对于第i行来说，该列对应的高度就是0。这个道理比较直观，简单说就是滚动数组height[j]的更新原则是看高度能不能在新的一行续上。这种滚动数组技巧的好处在于只需要维护一个一维数组，否则需要维护二维数组，是dp过程的常用技巧。

b) c) 如何找每个点向左（右）能推到的最远的位置？

这个部分更是精妙，不仅利用了滚动数组的技巧，而且还充分利用了上一轮dp的结果。以b)为例分析，c)同理。

在此题的背景下，当前行的某列能向左推到哪要考虑如下几种情况：

　　1）高度是是0（即matrix[i][j]=='1'不成立）：显然能推到最左侧即0的位置，不受上一行该列能向左推到哪的影响。

　　2）如果高度不是0（即matrix[i][j]=='1'成立），则这当前行该列能向左推到哪取决于左侧第一个不比它高的列在哪？

　　　考虑一个问题：在matrix[i][j]=='1'的前提下，第i行的l_most[j]可不可能比第i-1行的l_most[j]还小（即还往左）？

　　　显然，这是不可能的。因为第i行的j列已经把高度续上了，当且仅当第i行l_most[j]~j列的位置都满足高度续上的前提下，第i行的l_most[j]才可能等于第i-1行的l_most[j]；一旦第i行l_most[j]~j有一个位置没有续上高度，那么第i行的l_most[j]就要比第i-1行的l_most[j]小了.

　　　通过以上分析，在第i行j列已经把高度续上的前提下，能向左推到哪，关键取决于在j左边且最靠近j列没续上高度的列，是否影响到了l_most[j]~j。因此，维护一个l_curr，标记到当前列为止，续上高度的列最多可能向左推到哪。

　　　所以，需要比较l_most[j]与l_curr的位置。如果遇上了高度为0的，则自动把l_curr+1；如果高度不为0的，判断l_curr是否影响到了l_most[j]

　　　描述的比较绕口，但是客观上也就是这样了。

d) 计算可能的最大高度

这个就是个常规的dp，不再赘述了。注意一点就是（right-left+1）*height，这里是否“+1”取决于l_most和r_most的取值方式。

==============================================

第二次过这道题，思路记得比较清晰；具体操作上一些细节再熟练一下。

class Solution {

public:

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

        {

            int ret = ;

            if ( matrix.empty() ) return ret;

            vector<int> height(matrix[].size(), );

            for ( int i=; i<matrix.size(); ++i )

            {

                // update height

                for ( int j=; j<matrix[i].size(); ++j )

                {

                    height[j] = matrix[i][j]=='' ?  : height[j]+;

                }

                // update max area

                ret = max(ret, Solution::maxArea(height));

            }

            return ret;

        }

        static int maxArea(vector<int>& height)

        {

            int ret = ;

            height.push_back();

            stack<int> sta;

            for ( int i=; i<height.size(); ++i )

            {

                if ( sta.empty() || height[i]>height[sta.top()] )

                {

                    sta.push(i);

                    continue;

                }

                while ( !sta.empty() && height[sta.top()]>=height[i] )

                {

                    int tmp = sta.top();

                    sta.pop();

                    if ( sta.empty() )

                    {

                        ret = max( ret, i*height[tmp] );

                    }

                    else

                    {

                        ret = max(ret, (i-sta.top()-)*height[tmp] );

                    }

                }

                sta.push(i);

            }

            height.pop_back();

            return ret;

        }

};

巴特西

【Maximal Rectangle】cpp

最新文章

热门文章