leetcode題解分析_221. Maximal Square（圖文分析)

【題目】

題目連結

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

For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 4.

【分析】

dp

剛開始想的是

matrix[i-1][j-1]–>matrix[i][j]

vec[i][j]表示以該坐标為右下角的正方形的邊長

比如：

1 1 0

1 1 1

vec[0][0] = 1

vec[0][1] = 1

vec[0][2] = 0

vec[1][0] = 1

vec[1][1] = 2

vec[1][2] = 1

對于matrix[i][j]:

每次判斷matrix[i-1][j-1]後還需要從判斷matrix[i][ j- (1–>matrix[i-1][j-1]) ]是否有為’0’的情況，有的話終止循環，得到matrix[i][j]的值

舉例：

（紅色代表’1’,黃色代表’0’)

當我們周遊matrix[i][j]時，matrix[i][j]=’1’，為紅色

（1）找[i-1][j-1]，假設我們已經計算的vec[i-1][j-1]=3(即邊長為3，藍色方框中）

（2）就開始周遊matrix[i][ j- (1–>matrix[i-1][j-1]) ]==’0’?,一旦等于’0’,就終止，進而得到vec[i][j]的邊長

（3）上面的例子中我們看到matrix[i-3][j] == ‘0’(為黃色)，則得到以[i][j]為右下角的方形邊長頂多為3，即下面的黑框中的區域

是以這種做法的複雜度最壞O(n**3)

但是leetcode上的樣例比較小，是以這種做法也能跑得很好

runtime：

好了，下面我們來看O(n**2)的解法：

其實就是：

matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1]–>matrix[i][j] 很強

跑出來也是9ms

代碼：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) 
    {
        int rowSize = matrix.size();
        if(!rowSize) return ;
        int colSize = matrix[].size();
        if(!colSize) return ;
        int square[rowSize+][colSize+];
        memset(square, , sizeof(int)*(rowSize+)*(colSize+));
        int maxWidth = ;
        for(int r = ; r <= rowSize; ++r)
        {
            for(int c = ; c <= colSize; ++c)
            {
                if(matrix[r-][c-] == '1')
                    square[r][c] = min(min(square[r-][c], square[r][c-]), square[r-][c-]) + ;
                maxWidth = max(maxWidth, square[r][c]);
            }
        }
        return maxWidth*maxWidth;
    }
};
           

當然可以這樣寫：

int maximalSquare2(vector<vector<char>>& matrix) {
    int row = matrix.size();
    if( row ==  ) return ;
    int col = matrix[].size() , max_dis = ;
    vector<vector<int>> square( row+ , vector<int>( col +  ,  ) );
    for(int i = ; i <= row; ++i){
        for(int j = ; j <= col; ++j){
            if(matrix[i-][j-] == '1')
                square[i][j] = min(min(square[i-][j], square[i][j-]), square[i-][j-]) + ;
            max_dis = max(max_dis, square[i][j]);
        }
    }
    return max_dis*max_dis;
    }