221.最大正方形.md

221.最大正方形

/*
 * @lc app=leetcode.cn id=221 lang=typescript
 *
 * [221] 最大正方形
 */

// @lc code=start
function maximalSquare(matrix: string[][]): number {}
// @lc code=end

解法 1: 动态规划

• 状态: dp[i][j] 表示以 i,j 为右下角的最大正方形的边
• 递推公式:

  matrix[i][j] === 0 ? (dp[i][j] = 0) : (dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1)

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

  let [max, pre] = [0, 0]
  const dp = new Array(n).fill(0)
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const tmp = dp[j]
      if (matrix[i][j] === '0') dp[j] = 0
      else dp[j] = Math.min(pre, dp[j], dp[j - 1] ?? 0) + 1

      pre = tmp
      max = Math.max(max, dp[j])
    }
  }

  return Math.pow(max, 2)
}

Case

test.each([
  {
    input: {
      matrix: [
        ['1', '0', '1', '0', '0'],
        ['1', '0', '1', '1', '1'],
        ['1', '1', '1', '1', '1'],
        ['1', '0', '0', '1', '0'],
      ],
    },
    output: 4,
  },
  {
    input: {
      matrix: [
        ['0', '1'],
        ['1', '0'],
      ],
    },
    output: 1,
  },
  { input: { matrix: [['0']] }, output: 0 },
  { input: { matrix: [['1']] }, output: 1 },
  {
    input: {
      matrix: [
        ['0', '0', '0', '1'],
        ['1', '1', '0', '1'],
        ['1', '1', '1', '1'],
        ['0', '1', '1', '1'],
        ['0', '1', '1', '1'],
      ],
    },
    output: 9,
  },
])('input: matrix = $input.matrix', ({ input: { matrix }, output }) => {
  expect(maximalSquare(matrix)).toEqual(output)
})