leetcode 85. 最大矩形

题目链接：leetcode 85

1.题目

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

2.示例

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）示例 2：
输入：matrix = []
输出：0

3）示例 3：
输入：matrix = [[“0”]]
输出：0

4）示例 4：
输入：matrix = [[“1”]]
输出：1

5）示例 5：
输入：matrix = [[“0”,“0”]]
输出：0

6）提示：
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 ‘0’ 或 ‘1’

3.分析

刚开始相岔了，想到求最大正方形的那道题，f[i-1]由f[i-1][j-1]来递推，但是因为这是矩形，我们可以考虑当前格子由它上面那个格子递推。f[i][j][k]表示第i行第j列格子为矩形右下角顶点，且长为k的最大面积，那么k<=sum[i]j

4.代码

class Solution {
public:
    int sum[210][210],ans=0;
    int f[210][210][210];
    int maximalRectangle(vector<vector<char>>& matrix) {
        memset(sum,0,sizeof(sum));
        memset(f,0,sizeof(f));
        int rows=matrix.size(),cols=matrix[0].size();
        for(int i=0;i<rows;i++)
            if(matrix[i][0]=='1') sum[i][0]=1;
        for(int i=0;i<rows;i++)
            for(int j=1;j<cols;j++)
                if(matrix[i][j]=='1') sum[i][j]=sum[i][j-1]+1;
        for(int i=0;i<cols;i++)
            for(int j=0;j<=sum[0][i];j++)
                f[0][i][j]=j;
        for(int i=1;i<rows;i++)
            for(int j=0;j<cols;j++){
                for(int k=1;k<=sum[i][j];k++)
                        f[i][j][k]=max(f[i][j][k],k);
                for(int k=1;k<=min(sum[i][j],sum[i-1][j]);k++)
                    f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+k);
            }
        for(int i=0;i<rows;i++)
            for(int j=0;j<cols;j++)
                for(int k=0;k<=sum[i][j];k++)
                    ans=max(ans,f[i][j][k]);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30