LeetCode 热题 C++ 85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [["0"]]
输出：0

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

输入：matrix = [["0","0"]]
输出：0

思路：

和LeetCode 热题 C++ 84. 柱状图中最大的矩形_Zero_979的博客-CSDN博客

一样。

只不过这个需要一层一层地去算。

所以先一层层计算高度，然后调用就好了。

代码：

 

class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
        int len=heights.size();
        if(len==0)return 0;
        if(len==1)return heights[0];
        stack<int> s;
        int ans=0;
        s.push(0);
        heights.push_back(0);
        for(int i=1;i<=len;i++)
        {
            while(!s.empty()&&heights[s.top()]>heights[i]){
                int t=s.top();
                s.pop();
                int w=i;
                if(!s.empty())w=w-s.top()-1;
                ans=max(ans,w*heights[t]);
            }
            s.push(i);
        }
        return ans;
    }
    int maximalRectangle(vectorchar>>& matrix) {
        int w[205][205];
        memset(w,0,sizeof(w));
        int n=matrix.size();
        if(n==0)return 0;
        int m=matrix[0].size();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(matrix[i-1][j-1]!='0')w[i][j]=w[i-1][j]+1;
                else w[i][j]=0;
            }
        }
        int ans=0;
        vector<int> h;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++){
                h.push_back(w[i][j]);
            }
            ans=max(ans,largestRectangleArea(h));
            h.clear();
 
        }
        return ans;
    }
};