221. Maximal Square

這題我用的方法是一看到1, 就去看這個1能延伸到多少

class Solution {
public:
    int getMax(vector<vector<char>>& matrix, int i, int j){
        int m = matrix.size();
        int n = matrix[0].size();
        int len = 1;
        while(i + len <= m || j + len <= n){
            for(int p = i;p < i + len;p++){
               for(int q = j;q < j+ len;q++){
                    if(matrix[p][q] == '0'){
                        return (len -1) * (len -1);
                    }
               } 
            }
            len++;
            if(i + len > m || j + len > n){
                break;
            }
          
        }
        return (len -1) * (len -1);
    }
        
    int maximalSquare(vector<vector<char>>& matrix) {
        int res = 0;
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i = 0; i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == '1'){
                    res = max(res, getMax(matrix, i, j));
                }
            }
        }
        return res;
    }
};

但這題應該是要考dp, 當下還真沒想到

dp[i][j], 表示[i][j]位置最大的正方形邊長, ij為正方形的最右下角, 所以我們在設計上會先用看ij位置是否為1, 不是dp[i][j]就一定是0

因為我們接下來要看 i -1, j -1的狀況, 所以我們先排除掉如果i ==0 或j ==0的情況

當i或j == 0由於在最邊界的左上角一定沒有值, 所以我們就單純判斷他是不是1就好了

剩下的就是判定三個方向, 上方, 左方, 左上方, 三個點的值是否一致, 如果不是就會通常就會是1了, 我們用min直接對這三個點取最小值在加1比較方便

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int res = 0;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m;i++){
            for(int j = 0;j < n;j++){
                if(i == 0 || j == 0){
                    dp[i][j] = matrix[i][j] - '0';
                }else{
                    if(matrix[i][j] == '1'){
                        dp[i][j] = min({dp[i][j - 1], dp[i -1][j], dp[i-1][j-1]}) + 1;
                    }
                }
                if(dp[i][j]){
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }
};