[LintCode/LeetCode] Maximal Square

Drinkey 發(fā)布于2019-08-14 15:14 / 3199人閱讀

摘要：類似這種需要遍歷矩陣或數(shù)組來判斷，或者計算最優(yōu)解最短步數(shù)，最大距離，的題目，都可以使用遞歸。

Problem

Given a 2D binary matrix filled with 0"s and 1"s, find the largest square containing all 1"s and return its area.

Example

For example, given the following matrix:

Note

類似這種需要遍歷矩陣或數(shù)組來判斷True or False，或者計算最優(yōu)解（最短步數(shù)，最大距離，etc）的題目，都可以使用遞歸。
所以，找矩陣內(nèi)存在的最大正方形，需要：

構(gòu)造傳遞方程：用dpi存儲以當(dāng)前點matrixi作為正方形右下角頂點，所存在的最大正方形的邊長，由matrixi左、上、左上三點的dp值共同判定；

初始化邊界：matrix的第一列和第一行；

自頂向下遞推dp并更新max，找到max的最大值求平方得最優(yōu)解。

Corresponding dp matrix:

0 0 0 0 0 0 
0 1 0 1 0 0
0 1 0 1 1 1
0 1 1 1 2 2
0 1 0 0 1 0

mLen = 2, the maximum dp[i] = 2 appeared twice, indicating that there are two maximal squares.

Solution

public class Solution {
    public int maxSquare(int[][] matrix) {
        int mLen = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i-1][j-1] == 1) {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                    mLen = Math.max(mLen, dp[i][j]);
                }
            }
        }
        return mLen * mLen;
    }
}