首页 > 代码库 > Leetcode:Maximal Rectangle 最大全1子矩阵

Leetcode:Maximal Rectangle 最大全1子矩阵

Maximal Rectangle

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

解题分析:

联想到 最大矩形面积 这一题,可以在O(n)时间内求出 最大的矩形面积

如果我们把每一行看成x坐标,那高度就是从那一行开始往上数的1的个数。

利用 最大矩形面积 的方法,在O(n2)时间内就可以求出每一行形成的“柱状图”的最大矩形面积了

class Solution {public:    int maximalRectangle(vector<vector<char> > &matrix) {        int nRow = matrix.size();        if (nRow == 0) return 0;        int nCol = matrix.at(0).size();        std::vector<int> tmp(nCol, 0);        int result = 0;        for (int i = 0; i < nRow; ++i) {   // 计算每一行可以形成的最大矩形面积            for (int j = 0; j < nCol; ++j) {                if (matrix.at(i).at(j) == 0) {                    tmp.at(j) = 0;                } else {                    tmp.at(j)++;         // 计算当前行的当前列的累积高度(1的个数)                }            }            int area = largestRectangleArea(tmp);            result = std::max(result, area);        }        return result;    }        // 最大矩形面积    int largestRectangleArea(std::vector<int>& height) {        if (height.size() == 0) return 0;        height.push_back(-1);        std::stack<int> stk;        int result = 0;        for (int i = 0; i < height.size(); ) {            if (stk.empty() || height.at(i) > height.at(stk.top())) {                stk.push(i);                ++i;            } else {                int idx = stk.top();                stk.pop();                int area = height.at(idx) * (stk.empty() ? i : i - stk.top() - 1);                result = std::max(result, area);            }        }        return result;    }};

 

Leetcode:Maximal Rectangle 最大全1子矩阵