【LeetCode 85】最大矩形

【题解】

把所有的"1"矩形分成m类。
第j类的矩形。他的右边界跟第j列紧靠。
那么。
我们设f[i][j]表示(i,j)这个点往左最长能延伸多少个数目的"1"
那么对于第j类的矩形。
我们会发现。问题转化为求一个侧着放的柱状图。
然后让你在其中找到最大面积的矩形。且要求紧贴着底面(也即第j列)
那么问题就抓换成[这道题](https://www.cnblogs.com/AWCXV/p/11934410.html)了。
做一个O(N)的单调队列就能解决。
所以总的复杂度就是O(N^2)的。

【代码】

class Solution {

public:

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

        if (matrix.empty()) return 0;

        if (matrix[0].empty()) return 0;

        int n = matrix.size();

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

        int f[1005][1005];

        memset(f,0,sizeof(f));

        for (int i = 0;i < n;i++)

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

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

                    f[i+1][j+1] = f[i+1][j]+1;

                }

            }

        int h[1005],sta[1005];

        memset(h,0,sizeof(h));memset(sta,0,sizeof(sta));

        int top;

        int ma = 0;

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

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

                h[i] = f[i][j];

            }

            top = 1;

            sta[1] = 0;

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

                while (top!=1 && h[sta[top]]>h[i]){

                    ma = max(ma,h[sta[top]]*(i-1-sta[top-1]));

                    top--;

                }

                sta[++top] = i;

            }

            while (top>1){

                ma = max(ma,h[sta[top]]*(n-sta[top-1]));

                top--;

            }

        }

        return ma;

    }

};

巴特西

【LeetCode 85】最大矩形

最新文章

热门文章