中等

问题描述

在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi] 表示 grid[xi][yi] == 0

返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1，以及 4 个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。

示例 1：

输入: n = 5, mines = [[4, 2]]
输出: 2
解释: 在上面的网格中，最大加号标志的阶只能是 2。一个标志已在图中标出。

示例 2：

输入: n = 1, mines = [[0, 0]]
输出: 0
解释: 没有加号标志，返回 0 。

提示：

• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• 每一对 (xi, yi) 都 不重复

暴力枚举

构造矩阵，矩阵以 $1$ 填充，然后遍历 $mines$ ，将 $mines$ 中的点置 $0$，然后遍历矩阵中的点，若点的值为 $1$，则从该点开始，往上、下、左、右四个方向扩散，直到到达矩阵边界或者值为 $0$ 的点，过程中记录最大值即可。

/**
 * @param {number} n
 * @param {number[][]} mines
 * @return {number}
 */
var orderOfLargestPlusSign = function (n, mines) {
  const g = new Array(n).fill(0).map(() => new Array(n).fill(1))
  for (const [x, y] of mines) {
    g[x][y] = 0
  }
  let ans = 0
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (g[i][j]) {
        let cnt = 1
        while (
          i - cnt >= 0 &&
          i + cnt < n &&
          j - cnt >= 0 &&
          j + cnt < n &&
          g[i + cnt][j] &&
          g[i - cnt][j] &&
          g[i][j + cnt] &&
          g[i][j - cnt]
        ) {
          cnt++
        }
        ans = Math.max(ans, cnt)
      }
    }
  }
  return ans
}

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$

动态规划

构造矩阵 $g$，矩阵以 $1$ 填充，然后遍历 $mines$ ，将 $mines$ 中的点置 $0$，设 $dp[i][j][k]$ 表示以 $(i, j)$ 为起点在方向 $k$ （$k$ 取值 $0、1、2、3$ 代表上、下、左、右）上的连续 $1$ 的最大数目，可以得到以下递推式：

$$dp[i][j][0] = \begin{cases} 0 & g[i][j] = 0 \\ dp[i-1][j][0] + 1 & g[i][j] = 1 \\ \end{cases} \\ dp[i][j][1] = \begin{cases} 0 & g[i][j] = 0 \\ dp[i+1][j][1] + 1 & g[i][j] = 1 \\ \end{cases} \\ dp[i][j][2] = \begin{cases} 0 & g[i][j] = 0 \\ dp[i][j-1][2] + 1 & g[i][j] = 1 \\ \end{cases} \\ dp[i][j][3] = \begin{cases} 0 & g[i][j] = 0 \\ dp[i][j+1][3] + 1 & g[i][j] = 1 \\ \end{cases}$$

最终每个位置四个方向的最小值为该点最大的轴对齐加号标志的阶数，最终得到个点的最大值即为答案。

/**
 * @param {number} n
 * @param {number[][]} mines
 * @return {number}
 */
var orderOfLargestPlusSign = function (n, mines) {
  const g = new Array(n).fill(0).map(() => new Array(n).fill(1))
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(n))
  let ans = 0
  for (const [x, y] of mines) {
    g[x][y] = 0
  }
  for (let i = 0; i < n; i++) {
    let cnt = 0
    for (let j = 0; j < n; j++) {
      if (g[i][j]) {
        cnt++
      } else {
        cnt = 0
      }
      dp[i][j] = Math.min(dp[i][j], cnt)
    }
    cnt = 0
    for (let j = n - 1; j >= 0; j--) {
      if (g[i][j]) {
        cnt++
      } else {
        cnt = 0
      }
      dp[i][j] = Math.min(dp[i][j], cnt)
    }
  }
  for (let i = 0; i < n; i++) {
    let cnt = 0
    for (let j = 0; j < n; j++) {
      if (g[j][i]) {
        cnt++
      } else {
        cnt = 0
      }
      dp[j][i] = Math.min(dp[j][i], cnt)
    }
    cnt = 0
    for (let j = n - 1; j >= 0; j--) {
      if (g[j][i]) {
        cnt++
      } else {
        cnt = 0
      }
      dp[j][i] = Math.min(dp[j][i], cnt)
      ans = Math.max(ans, dp[j][i])
    }
  }
  return ans
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$