LeetCode 1139. 最大的以 1 為邊界的正方形

截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666

前面我們講過《530，動態規劃解最大正方形》，第530題需要正方形所有網格中的數字都是1，只要搞懂動態規劃的原理，代碼就非常簡潔，而這題只要正方形4條邊的網格都是1即可，中間是什么數字不用管，相對來說這題難度要比第530題稍微大一些，

這題解題思路是這樣的

• 第一步先計算每個網格中橫向和豎向連續1的個數，
• 第二步遍歷二維網格，以每一個格子為正方形的右下角，分別找出上邊和左邊連續1的個數，取最小值作為正方形的邊長，然后判斷正方形的左邊和上邊長度是否都大于等于正方形邊長，如果都大于等于正方形邊長就更新正方形的最大邊長，否則縮小正方形的邊長，繼續判斷……，

如果看不懂也沒關系，我們一步一步來，等分析完之后回過頭來看，你會恍然大悟，原來這么簡單，

1，第一步，計算橫向和豎向連續1的個數，舉個例子，

代碼比較簡單，我們定義一個三維陣列，其中

• dp[i][j][0]: (i,j)橫向連續1的個數
• dp[i][j][1]: (i,j)豎向連續1的個數

我們計算的時候，如果當前位置是0就跳過，只有是1的時候才計算，分別統計左邊和上邊（也就是橫向和豎向）連續1的個數，代碼比較簡單，我們來看下（這里為了減少一些邊界條件的判斷，把dp的寬和高都增加了1），

int m = grid.length;
int n = grid[0].length;
//dp[i][j][0]: (i,j)橫向連續1的個數
//dp[i][j][1]: (i,j)豎向連續1的個數
int[][][] dp = new int[m + 1][n+1][2];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        //如果當前位置是0，就跳過
        if (grid[i - 1][j - 1] == 0)
            continue;
        //如果是1，我們就計算橫向和豎向連續1的個數
        dp[i][j][0] = dp[i][j - 1][0] + 1;
        dp[i][j][1] = dp[i - 1][j][1] + 1;
    }
}

2，第二步，找出正方形的最大邊長

我們會以網格中的每一個位置為正方形的右下角，來找出正方形的邊長，如下圖所示，我們以橙色的位置1為正方形的右下角，分別沿著左邊和上邊找出他們連續1的個數，最小的作為正方形的邊長，因為左邊和上邊連續1的個數我們在第一步的時候已經計算過，分別是dp[i][j][0]和dp[i][j][1]，也就是正方形的邊長我們暫時可以認為是，

int curSide = Math.min(dp[i][j][0], dp[i][j][1]);

其實大家已經看到了這個邊長就是正方形下邊和右邊的長度，但是正方形的上邊和左邊我們還沒確定，我們繼續確定正方形左邊和上邊的長度，會有兩種情況

一種如下圖所示，就是正方形左邊和上邊的長度都大于curSide，我們可以認為以坐標(i,j)為右下角的正方形的最大長度就是curSide，

另一種如下圖所示，正方形上邊的長度是1，小于curSide，

這種情況下是構不成正方形的，所以我們要縮小curSide的值，然后再繼續判斷……

搞懂了上面的程序，代碼就簡單多了，我們來直接看下代碼，

public int largest1BorderedSquare(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    //dp[i][j][0]: (i,j)橫向連續1的個數
    //dp[i][j][1]: (i,j)豎向連續1的個數
    int[][][] dp = new int[m + 1][n + 1][2];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //如果當前位置是0，就跳過
            if (grid[i - 1][j - 1] == 0)
                continue;
            //如果是1，我們就計算橫向和豎向連續1的個數
            dp[i][j][0] = dp[i][j - 1][0] + 1;
            dp[i][j][1] = dp[i - 1][j][1] + 1;
        }
    }
    int maxSide = 0;//記錄正方形的最大長度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //沿著當前坐標往上和往左找出最短的距離，暫時看做是正方形的邊長(正方形的具體邊長
            //還要看上邊和左邊的長度，所以這里要判斷一下)
            int curSide = Math.min(dp[i][j][0], dp[i][j][1]);
            //如果邊長小于maxSide，即使找到了也不可能再比maxSide大，所以我們沒必要再找，直接跳過，
            if (curSide <= maxSide)
                continue;
            //curSide可以認為是正方形下邊和右邊的長度，我們還需要根據正方形上邊和左邊的長度
            //來確認是否滿足正方形的條件
            for (; curSide > maxSide; curSide--) {
                //判斷正方形的左邊和上邊的長度是否大于curSide，如果不大于，我們就縮小正方形
                //的長度curSide，然后繼續判斷
                if (dp[i][j - curSide + 1][1] >= curSide && dp[i - curSide + 1][j][0] >= curSide) {
                    maxSide = curSide;
                    //更短的就沒必要考慮了，這里直接中斷
                    break;
                }
            }
        }
    }
    //回傳正方形的邊長
    return maxSide * maxSide;
}

時間復雜度：O(m*n*min(m,n))，m和n分別是矩陣的寬和高
空間復雜度：O(m*n)，使用了一個三維陣列(m*n*2)