最大正方形(Maximal Square)

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：
图裂了

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：
图裂了

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

int min(int a, int b){
    if (a<b){
        return a;
    }else{
        return b;
    }
}

bool noZero(char** matrix, int row ,int col ,int size){
    for(int dr = 0;dr < size;dr++){
        for(int dc = 0;dc < size; dc++){
            if(matrix[row+dr][col+dc] == '0'){
                return false;
            }
        }
    }
    return true;
}

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    // if (matrixSize == 0) return 0;
    int rows = matrixSize;
    int cols = matrixColSize[0];

    int maxSize = 0;
    for(int row =0 ;row < rows;row++){
        for(int col = 0;col<cols; col++){
            for(int size =1;size<=min(rows-row,cols-col);size++){
                if(noZero(matrix, row, col, size) && size > maxSize){
                    maxSize = size;
                }
            }
        }
    }
    return maxSize * maxSize;
}

勉强过了

int max2(int a,int b){
    return a>b?a:b;
}
int min2(int a,int b){
    return a<b?a:b;
}
int min3(int a, int b, int c){
    return min2(min2(a,b),c);
}

int findMaximalSquareBottomLeftOne(char** matrix, int rows, int cols,int **cache2) {
    if(rows == 0 || cols==0) return 0;
    if(matrix[rows-1][cols-1] == '0') return 0;

    if(cache2[rows][cols] != -1) return cache2[rows][cols];
    cache2[rows][cols] = min3(
            findMaximalSquareBottomLeftOne(matrix, rows-1, cols, cache2),
            findMaximalSquareBottomLeftOne(matrix, rows, cols-1, cache2),
            findMaximalSquareBottomLeftOne(matrix, rows-1, cols-1, cache2))+1;

    return cache2[rows][cols];
}

int findMaximalSquare(char** matrix ,int rows , int cols, int** cache1, int** cache2){
    if(rows == 0 || cols==0) return 0;

    if(cache1[rows][cols] != -1) return cache1[rows][cols];

    cache1[rows][cols] =
            max2(
                    max2(
                            findMaximalSquare(matrix, rows-1, cols, cache1,cache2),
                            findMaximalSquare(matrix, rows, cols-1,cache1,cache2)),


                            findMaximalSquareBottomLeftOne(matrix,rows,cols,cache2));

    return cache1[rows][cols];
}

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    if(matrixSize == 0) return 0;

    int rows = matrixSize;
    int cols = matrixColSize[0];

    int** cache1 = malloc((rows+1)*sizeof(int*));
    int** cache2 = malloc((rows+1)*sizeof(int*));
    for(int row = 0; row<=rows; row++){
        cache1[row] = malloc((cols+1)*sizeof(int));
        cache2[row] = malloc((cols+1)*sizeof(int));
    }
    for(int row = 0; row<= rows; row++){
        for(int col=0; col<=cols; col++){
            cache1[row][col] = -1;
            cache2[row][col] = -1;
        }
    }

    int answer = findMaximalSquare(matrix, rows, cols, cache1, cache2);

    for(int row = 0;row <= rows; row++){
        free(cache1[row]);
        free(cache2[row]);
    }
    free(cache1);
    free(cache2);
    return answer*answer;
}

再次经典空间换时间，368ms一下跃迁到了20ms

int max2(int a,int b){
    return a>b?a:b;
}
int min2(int a,int b){
    return a<b?a:b;
}
int min3(int a, int b, int c){
    return min2(min2(a,b),c);
}

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    if(matrixSize == 0) return 0;
    int** maximalSquareBottomLeft = malloc((matrixSize+1)*sizeof(int*));
    for(int row = 0; row<=matrixSize; row++){
        maximalSquareBottomLeft[row] = calloc((matrixColSize[0]+1),sizeof(int));
    }

    int answer = 0;
    for(int rows =1;rows <= matrixSize;rows++) {
        for(int cols = 1;cols <= matrixColSize[0]; cols++) {
            if(matrix[rows-1][cols-1] == '1') {
                maximalSquareBottomLeft[rows][cols] =
                        min3(
                                maximalSquareBottomLeft[rows-1][cols],
                                maximalSquareBottomLeft[rows][cols-1],
                                maximalSquareBottomLeft[rows-1][cols-1])+1;
            }
            answer = max2(answer, maximalSquareBottomLeft[rows][cols]);
        }
    }
    for(int row = 0;row <= matrixSize; row++){
        free(maximalSquareBottomLeft[row]);
    }
    free(maximalSquareBottomLeft);
    return answer*answer;
}

时间没减少，内存消耗变少了