【Leetcode HOT100】最大正方形 c++

题目描述：

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4

示例 2：

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1

示例 3：

输入：matrix = [[“0”]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’

c++代码：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int dp[m][n]; //dp[i][j]表示以i，j为右下角的正方形最大边长（面积等于边长*边长）
        int maxsum = 0;
        for(int i=0;i<m;i++){ 
            if(matrix[i][0]=='1'){
                dp[i][0]=1; //j=0初始化
                maxsum=1;
            }
            else dp[i][0]=0;
        }
        for(int i=0;i<n;i++){ 
            if(matrix[0][i]=='1'){
                dp[0][i]=1; //i=0初始化
                maxsum=1;
            }
            else dp[0][i]=0;
        }
        for(int i=1;i<m;i++){ 
            for(int j=1;j<n;j++){
                if(matrix[i][j]=='1'){
                    dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
                    if(dp[i][j]>maxsum)maxsum=dp[i][j];
                }    
                else dp[i][j]=0;
            }
        }
        return maxsum*maxsum;
    }
};
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
31
32
33

首先，要求的最大正方形面积，简化为最大正方形边长。

其次，全为1的最大正方形，可以由全为1的小正方形不断拓展扩大得到，所以以右下角的位置作为正方形区分的标志更容易，采用动态规划。

最小的全1正方形：当格子本身为1时，边长为1
次小的全1正方形：当前格子本身为1，右下角格子的左边，左上角，上方格子都为1，边长为2
…

即对于每个右下角值为1的格子，考察其相邻的三个格子的dp值，更新正方形的最大边长。

dp[i][j]表示以(i,j)为右下角的全为1的正方形的最大边长。

若当前格子本身为1，dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1
若当前格子本身为0，则dp[i][j]=0

初始化最上边和最左边的起始dp（i=0或j=0时）：若格子为1，dp[i][j]=1；否则dp[i][j]=0