Leetcode — 221. Maximal Square (中文)

問題連結: https://leetcode.com/problems/maximal-square/

給予m x n 的二維陣列 matrix , 陣列裡面只包含 0或1
求這個陣列中, 只由1組成的最大正方形面積

範例 
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4 (shown in below graph)

example graph (Photo Credit to Leetcode)

想法:

一開始會想說這題會不會跟Number of Islands很像, 在Number of Islands裡面, 我們可以用DFS來找連著他的所有是1的格子, 把他們全部都merge成一格再來數總共有幾個這樣的格子
但這題又不太一樣, 因為題目規定一定要是正方形才算數, 長方形或者任何不規則的圖形都不能算進我們的條件裡, 因此看來用DFS不能輕鬆解決這題

🔲如果只是要找長度為1的正方形就很簡單, 只要有一格是1就可以了; 那如果要找到長度是2或更高長度的正方形的話呢?

假設我們從整個題目給的matrix的左上角開始走訪每個格子(也就是從(0,0)開始, 慢慢往右走 走完在往下一行開始走), 那代表我們第一個碰到某個潛在正方形的點就是正方形的左上角, 那我們要如何知道這個就是我們要找的?

如果只要找長度是2的正方形那還算簡單, 我們可以直接看現在位置(i,j)的右側, 下側, 及右下格就好, 如果他們都是1, 我們就可以確認這是個長度為2的正方形
如果是3, 那就沒有那麼容易了, 除了右, 下, 右下, 我們還要找 右右, 下下, 右下的右下, … 總共要檢查8格! 更長的長度就以此類推, 一個一個慢慢找實在太慢

但是如果我們把一個n*n的正方形畫下來, 我們可以發現一個"規律", 我們一定可以在n*n的正方形裡面組成4個重疊的 (n-1)*(n-1) 的正方形
如下圖所示

3x3的正方形中有4個2x2的小正方形

當我們把各個正方形的左上角的格子寫下這個正方形的最長長度時, 就會如下圖所示, 我們可以清楚的看到3被3個2包圍, 這也是因為我們上述提到的特性, 當我們可以組成4個(包含自己) 2*2的正方形時, 代表這裡可以組成一個3*3的正方形,
因此想知道某位置(i,j) 最長可以組成多少長度的正方形, 我們只要注意其右方格, 右下格, 及下方格 的數字即可, 而我們程式碼將利用這個特性來幫忙找最長長度的正方形

僅在正方形的左上格寫下從這格可以組成正方形的最長長度

程式邏輯:

因為我們需要利用別的格子(右,下方, 右下方)來判斷我們這個格子的最長長度, 因此用一個二維陣列來幫我們儲存值是很重要的 (也就是運用動態規劃dynamic programming)

程式邏輯則就是我們會參考右格, 下格, 右下格 之中 長度最短的長度 再加1, 視為我們可以從這格組成的正方形最長長度 (下方有例子解釋為何)

⚠️兩個特別注意的點:

1. 我們的陣列走訪方向是從陣列的最右下角(m-1, n-1)慢慢回去左上角(0,0)
   原因是因為既然每個格子都需要參考其右格, 下格 跟右下方的格子, 我們當然需要先把那些格子的值都安置好, 才能拿來參考!
2. 當格子是在最右側那直行,或最下層那橫排, 我們因為沒有右側或下側格子可以跟著那個格子一起組成正方形, 因此這些格子至多只能組成長度為1的正方形

👷為何可以直接認定這個位置可組成最大的長度是找鄰近三格中的最短長度又加1 ❓

其實又可以解釋成, 我們要找鄰近三格中他們保證可幫忙組成的最高長度, 又加1則是因為包含現在位置,我們可以擴展新的正方形
可看下面3個例子- 皆假設我們現在位置在(0,0), 要找從現在位置最長可以組成長度為何的正方形

🚧1. 假設matrix長這樣…

matrix範例(1)

參考附近格的"最長正方形長度值"
右格(0,1)的值為3, 下格(1,0)為0, 右下格(1,1)為2
因此我們只能取下格0, 再加長度1, 因此從(0,0)可組成的最長長度為1

🚧2. 假設matrix長這樣…

matrix範例(2)

參考附近格的”最長正方形長度值”
右格(0,1)的值為2, 下格(1,0)為2, 右下格(1,1)為1
因此我們只能取右下格1, 再加長度1, 因此從(0,0)可組成的最長長度為2

🔧從這裡我們就可以看出為何保證一定長度有2了, 因為右格跟下格都最多能組長度2, 代表他們可以保證他們周邊距離為2的格子都是1)

🚧3. 假設matrix長這樣…

matrix 範例(3)

參考附近格的”最長正方形長度值”
右格(0,1)的值為3, 下格(1,0)為2, 右下格(1,1)為2
因此我們只能取最小長度2, 再加長度1, 因此從(0,0)可組成的最長長度為3

🔧同上一個例子, 這次是 我們最多只能保證從右格, 下格, 跟右下格周邊長度2內 皆為1 代表我們從(0,0) 可以延伸成長度為3的正方形了 👷

以下為4ms的程式碼, 贏過87%的人 —

public int maximalSquare(char[][] matrix) {
        int max = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
                if(matrix[i][j]=='0')
                    continue;
                if(i==m-1||j==n-1)
                    dp[i][j] = 1;
                else
                {
                    dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]);
                    dp[i][j] = 1+Math.min(dp[i+1][j+1],dp[i][j]);
                }
                if(dp[i][j] > max)
                    max = dp[i][j];
            }
        }
        return max*max;
    }

⚠️若你只習慣從左上角開始走訪matrix, 也可以變成把正方形最長長度都寫在正方形的右下角, 因此檢查的點也變成是 每每檢查其 左格, 上格, 跟左上格 像這樣:

public int maximalSquare(char[][] matrix) {
        int max = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]=='0')
                    continue;
                if(i==0||j==0)
                    dp[i][j] = 1;
                else
                {
                    dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]);
                    dp[i][j] = 1+Math.min(dp[i][j],dp[i-1][j-1]);
                }
                if(dp[i][j]>max)
                    max = dp[i][j];
            }
        }
        return max*max;
    }