[LeetCode] 221、最大正方形

题目描述

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

示例：

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4
           

解题思路

85题的简化版。此题用动态规划，同样，状态表示和状态转移方程不看题解自己不好想。

• 动态规划

  • dp[i][j]

    表示以坐标

    (i,j)

    为右下角元素的最大正方形的边长。
  • 在

    matrix[i][j] == "1"

    ，情况下：

    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

    若某格子值为

    1

    ，则以此为右下角的正方形的最大边长为：上面的正方形、左面的正方形和左上的正方形中最小的那个，再加上此格（+1）。

    if (grid(i,  j) == 1) {
    	dp(i, j) = min(dp(i-1,  j),  dp(i,  j-1),  dp(i-1,  j-1)) + 1;
    }
               

  

  由“木桶原理”可知：

  ?

  附近的最小边长，才与

  ?

  的最长边长有关。
  • 初始化二维

    dp

    数组全为0。
  • 在不断的迭代和状态转移的过程中，不断更新

    maxRes

    并最终返回。

参考代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if(rows == 0)
            return 0;
        int cols = matrix[0].size();

        // 为了求解方便，构造多一个长度的二维数组！
        int dp[rows+1][cols+1];
        memset(dp, 0, sizeof(dp));
        int maxAns = 0;
        for(int i = 1; i <= rows; i++){
            for(int j = 1; j <= cols; j++){
                if(matrix[i-1][j-1] == '1')
                    dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;  // 别忘 +1

                maxAns = max(maxAns, dp[i][j]);
            }
        }

        return maxAns * maxAns;
    }
};