85. Maximal Rectangle

problem description

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

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

algorithm thought

求出矩阵中的最大矩形，可以利用动态规划的思路求解。首先定义一个left数组，保存节点高度可以最左到哪个节点，再定义一个right数组，保存节点高度最右可以到哪个节点。然后还有height数组，保存当前节点的高度。最后我们从以为矩阵开始，慢慢加高维度。起始时，left数组初始化为0，right数组初始化为size-1。然后定义一个curleft和curright，每当当前节点为0的时候，就要改变curleft和currgiht，当节点为1的时候，改变right和left数组。具体行为可以看代码理解。

code

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0||matrix[0].size()==0)
            return 0;
        vector<int> fromleft(matrix[0].size(),0);
        vector<int> fromright(matrix[0].size(),matrix[0].size());
        vector<int> height(matrix[0].size(),0);
        
        int res=0;
        for(int i=0;i<matrix.size();++i){
            int curleft=0;
            for(int j=0;j<matrix[0].size();++j){
                if(matrix[i][j]=='0'){
                    curleft=j+1;
                    fromleft[j]=0;
                }else{
                    fromleft[j]=max(fromleft[j],curleft);
                }
            }
            int curright=matrix[0].size()-1;
            for(int j=matrix[0].size()-1;j>=0;--j){
                if(matrix[i][j]=='0'){
                    curright=j-1;
                    fromright[j]=matrix[0].size()-1;
                }else{
                    fromright[j]=min(fromright[j],curright);
                }
            }
            for(int j=0;j<matrix[0].size();++j){
                if(matrix[i][j]=='0'){
                    height[j]=0;
                    continue;
                }
                height[j]++;
                res=max(res,height[j]*(fromright[j]-fromleft[j]+1));
            }
        }
        return res;
    }
};

algorithm analysis

有一个大循环，循环中进行3次遍历。相当于对二维数组进行遍历，时间复杂度O(n²)