[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;
    }
};