【leetcode】Maximal Rectangle (hard)★

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

找到01矩形中最大的全1子矩阵。

我自己的思路：

我先用一个跟输入相同大小的矩阵numInCol 存储从当前位置开始向下有多少连续的1。

　　如

其numInCol 是

然后用一个变量tmpans来记录以某个位置开始，其右下矩形的最大全1矩阵的大小。

方法是如果当前位置是1，则用1 * numInCol[当前位置] 即只有这一列的大小

如果其后面紧接着的位置也是1，则用 2 * (这两列中连续1高度小的值) 即这两列的矩形大小

如果其后面紧接着的位置也是1，则用 3 * (这三列中连续1高度小的值) 即这三列的矩形大小

........................

依次类推

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

using namespace std;

class Solution {

public:

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

        if(matrix.empty())

            return ;

        int row = matrix.size();

        int col = matrix[].size();

        int ans = ;

        vector<vector<int> > numInCol(row, vector<int>(col, ));

        int tmpans = ;

        //对每一列

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

        {

            numInCol[row - ][j] = (matrix[row - ][j] == '') ?  : ;

            for(int i = row - ; i >= ; i--)

            {

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

                {

                    numInCol[i][j] = numInCol[i + ][j] + ;

                }

            }

        }

        //对整个矩阵

        for(int i = row - ; i >= ; i--)

        {

            tmpans = numInCol[i][col - ];

            ans = max(ans, tmpans);

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

            {

                int jj = j;

                int len = ;

                int minlen = numInCol[i][j];

                while(jj < col && matrix[i][jj] == '')

                {

                    minlen = min(minlen, numInCol[i][jj]);

                    tmpans = max(tmpans, len * minlen);

                    ans = max(ans, tmpans);

                    jj++;

                    len++;

                }

            }

        }

        return ans;

    }

};

int main()

{

    Solution s;

    vector<vector<char> > matrix(, vector<char>(, ''));

    matrix[][] = '';

    matrix[][] = '';

    matrix[][] = '';

    matrix[][] = '';

    matrix[][] = '';

    matrix[][] = '';

    matrix[][] = '';

    matrix[][] = '';

    int ans = s.maximalRectangle(matrix);

    return ;

}

网上的答案，整体的思路差不多，也是通过一列列的数据来判断，但是并没有像我一样，把所有的值都存下来，而是只存了一行的列信息，每到新的一行再更新，这样空间少了很多。其次，没有像我这样每次都循环后面的列是否为1，而是利用栈，如果高度是递增的就先不计算最大矩形而是把信息压栈，等到遇到高度减少的时候再依次计算这一段的最大矩形。

class Solution {

public:

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

        if (matrix.empty()) return ;

        int rows = matrix.size();

        int cols = matrix[].size();

        int maxArea = ;

        vector<int> heights(cols + , );

        vector<int> stack;

        for (int i = ; i < rows; i++) {

            stack.clear();

            for (int j = ; j < cols + ; j++) {

                if (j < cols) {

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

                        heights[j]++;

                    } else {

                        heights[j] = ;

                    }

                }

                if (stack.empty() || heights[j] >= heights[stack.back()]) {

                    stack.push_back(j);

                    continue;

                }

                while (!stack.empty() && heights[j] < heights[stack.back()]) {

                    int top = stack.back();

                    stack.pop_back();

                    int begin = stack.empty() ?  : stack.back() + ;

                    int area = heights[top] * (j - begin);

                    if (area > maxArea) maxArea = area;

                }

                stack.push_back(j);

            }

        }

        return maxArea;

    }

};

巴特西

【leetcode】Maximal Rectangle (hard)★

最新文章

热门文章