同一矩阵上的最大平方 dp

Question

https://leetcode.com/problems/maximal-square/description/中的Maximal Square题，DP很容易解决。但我没有创建新矩阵，而是修改了原始矩阵，但该方法因测试用例 64 号而失败，请检查我的以下代码并帮助我找出缺失点。

def maximalSquare(self, matrix: List[List[str]]) -> int:

    for x in range(1,len(matrix)):
        for y in range(1,len(matrix[x])):
            if matrix[x][y] == '1':
                matrix[x][y] = str(int(min( matrix[x-1][y], matrix[x][y-1], matrix[x-1][y-1]))+1)

    return int(max([max(x) for x in matrix])) ** 2 if matrix else 0

Answer 1

我猜你没有处理极端情况。对我来说，这段代码运行只需稍加改动就可以了。另外，这会运行有点慢。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        m, n, res = len(matrix), len(matrix[0]), 0
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0) and (matrix[i][j] == '1'):
                    res = max(res, 1)
                elif int(matrix[i][j]) == 1:
                    matrix[i][j] = min(int(matrix[i-1][j]), int(matrix[i][j-1]), int(matrix[i-1][j-1])) + 1
                    res = max(res, matrix[i][j])
        return res ** 2

迭代第一行或第一列时，dp(i, j) 的公式正在检查是否存在越界值。通过将整个 dp 向右和底部移动 1，并将 0 填充到第 1 行和第 1 列，它使公式在不检查边界的情况下工作。

同一矩阵上的最大平方 dp

Maximal square dp on same matrix

algorithm

dynamic-programming

python-3.7