leetcode#85 最大矩阵

题目链接

分析

• 预处理好$f$ 函数，其含义如下：

  f[i][j][k]=
      从 Matrix[i][j] 往上数有多少个连续的1, k=0  
      从 Matrix[i][j] 往左数有多少个连续的1, k=1

• 接下来遍历整个矩阵的各个位置时，考虑以这个矩阵为右下角，能往左和往上扩展的最大矩阵的面积是多少，维护一个单调栈即可。

代码

class Solution {
public:
    int dp[205][205][2];    // 0,row; 1,col.
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();

        int ans=0;
        if(matrix[0][0]=='1'){
            dp[0][0][0]=dp[0][0][1]=1;
            ans=1;
        }
        else{
            dp[0][0][0]=dp[0][0][1]=0;
        }
    
        for(int i=1;i<rows;i++){
            if(matrix[i][0]=='1'){
                dp[i][0][0]=dp[i-1][0][0]+1;
                dp[i][0][1]=1;
            }
            else{
                dp[i][0][0]=dp[i][0][1]=0;
            }
            ans=max(dp[i][0][0],ans);
        }
        for(int i=1;i<cols;i++){
            if(matrix[0][i]=='1'){
                dp[0][i][0]=1;
                dp[0][i][1]=dp[0][i-1][1]+1;
            }
            else{
                dp[0][i][0]=dp[0][i][1]=0;
            }
            ans=max(dp[0][i][1],ans);
        }

        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                if(matrix[i][j]=='1'){
                    dp[i][j][0]=dp[i-1][j][0]+1;
                    dp[i][j][1]=dp[i][j-1][1]+1;
                }
                else{
                    dp[i][j][0]=dp[i][j][1]=0;
                }
            }
        }
    
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                if(matrix[i][j]=='1'){
                    int tmp1=dp[i][j][0];
                    int tmp2=1;
                    ans=max(ans,tmp1*tmp2);
                    while(j-tmp2>=0 && tmp1){
                        tmp1=min(tmp1,dp[i][j-tmp2][0]);
                        tmp2++;
                        ans=max(ans,tmp1*tmp2);
                    }

                    tmp1=dp[i][j][1];
                    tmp2=1;
                    while(i-tmp2>=0 && tmp1){
                        tmp1=min(tmp1,dp[i-tmp2][j][1]);
                        tmp2++;
                        ans=max(ans,tmp1*tmp2);
                    }
                }
            }
        }

        return ans;
    }
};