个人技术分享

代码实现：

方法一：模拟——超时

int maximalSquare(char **matrix, int matrixSize, int *matrixColSize) {
    int maxSide = 0;
    if (matrix == NULL || matrixColSize == NULL || matrixSize <= 0 
                                        || matrixColSize[0] <= 0) {
        return 0;
    }
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixColSize[0]; j++) {
            if (matrix[i][j] == '1') { // 起点
                int k = 1;
                int flag = 1;
                while (flag) {
                    if (i + k >= matrixSize || j + k >= matrixColSize[0]) {
                        flag = 0;
                        break;
                    }
                    for (int x = i; x <= i + k && x < matrixSize; x++) {
                        for (int y = j; y <= j + k && y < matrixColSize[0]; y++) {
                            if (matrix[x][y] == '0') {
                                flag = 0;
                                break;
                            }
                        }
                        if (!flag) {
                            break;
                        }
                    }
                    if (!flag) {
                        break;
                    }
                    k++;
                }
                if (maxSide < k) {
                    maxSide = k;
                }
            }
        }
	}
    return maxSide * maxSide;
}

方法二：动态规划

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))

int maximalSquare(char **matrix, int matrixSize, int *matrixColSize) {
    int maxSide = 0;
    int dp[matrixSize][matrixColSize[0]];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < matrixSize; i++) {
        if (matrix[i][0] == '1') {
            maxSide = max(maxSide, 1);
            dp[i][0] = 1;
        }
    }
    for (int j = 0; j < matrixColSize[0]; j++) {
        if (matrix[0][j] == '1') {
            maxSide = max(maxSide, 1);
            dp[0][j] = 1;
        }
    }
    for (int i = 1; i < matrixSize; i++) {
        for (int j = 1; j < matrixColSize[0]; j++) {
            if (matrix[i][j] == '1') {
                dp[i][j] = min((min(dp[i - 1][j], dp[i - 1][j - 1])), 
                                                    dp[i][j - 1]) + 1;
            }
            if (maxSide < dp[i][j]) {
                maxSide = dp[i][j];
            }
        }
    }
    return maxSide * maxSide;
}