Skip to main content

221. Maximal Square

分析

解法一是在每一点都去尝试以该点为正方形的左上角,利用dfs尽可能的增大,麻烦之处在于没有子状态可以借助,因此不方便缓存

解法2利用子状态

const ret = Math.min(
dfs(i, j + 1),
dfs(i + 1, j),
dfs(i + 1, j + 1)
) + 1

还可以转 dp

题解

超时最后一个

Pasted image 20220520223715.png

function maximalSquare(matrix: string[][]): number {
const n = matrix.length
const m = matrix[0].length
let ans = 0
const dfs = (x: number, y: number, len: number) => {
if (!isSquare(x, y, len)) {
return
}
ans = Math.max(ans, len * len)
dfs(x, y, len + 1)
}

const isSquare = (x: number, y: number, len: number): boolean => {
if (x + len > n || y + len > m) {
return
}
for (let i = x; i < x + len; i++) {
for (let j = y; j < y + len; j++) {
if (matrix[i][j] === "0") {
return false
}
}
}

return true
}

for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
dfs(i, j, 1)
}
}

return ans
};

解法2

function maximalSquare(matrix: string[][]): number {
const m = matrix.length, n = matrix[0].length

// 以[i][j] 作为正方形的左上角,最大正方形为
const memo: {
[key: string]: number
} = {}
const dfs = (i: number, j: number): number => {
// 图内
if (i >= m || j >= n) {
return 0
}
if (matrix[i][j] === "0") {
return 0
}

const memoKey = `${i}-${j}`

if (memo[memoKey] !== undefined) {
return memo[memoKey]
}

const ret = Math.min(
dfs(i, j + 1),
dfs(i + 1, j),
dfs(i + 1, j + 1)
) + 1
memo[memoKey] = ret

return ret
}

for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
dfs(i, j)
}
}

const maxLen = Math.max(...Object.values(memo), 0)

return maxLen * maxLen
};

根据解法2

function maximalSquare(matrix: string[][]): number {
const m = matrix.length, n = matrix[0].length
const dp: number[][] = Array.from({ length: m }, () => new Array(n))
// 处理边界情况
// 最后一行
for (let i = 0; i < n; i++) {
if (matrix[m - 1][i] === "0") {
dp[m - 1][i] = 0
} else {
dp[m - 1][i] = 1
}
}
// 最后一列
for (let i = 0; i < m; i++) {
if (matrix[i][n - 1] === "0") {
dp[i][n - 1] = 0
} else {
dp[i][n - 1] = 1
}
}

for (let i = m - 2; i >= 0; i--) {
for (let j = n - 2; j >= 0; j--) {
if (matrix[i][j] === "0") {
dp[i][j] = 0
continue
}
dp[i][j] = Math.min(
dp[i + 1][j],
dp[i][j + 1],
dp[i + 1][j + 1]
) + 1
}
}

return Math.pow(Math.max(...dp.flat()), 2)
};