跳到主要内容

764.最大加号标志

· 阅读需 3 分钟

1、题干​

在一个 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) 都 不重复​​​​​​​

Problem: 764. 最大加号标志

2、思路​

  • 暴力：遍历矩阵 grid，把每个网格当成中心，计算加号标志的最大阶数 k
  • 哈希：把 0 网格的坐标转换成哈希表降低查找时间复杂度
  • 剪枝：遍历过程中，通过当前求得的最大阶数 k 进一步缩小遍历范围

3、Code​

function orderOfLargestPlusSign(n: number, mines: number[][]): number {
    const M = 10007, hash = (x: number, y: number) => x * M + y;
    const set = new Set(mines.map(([x, y]) => hash(x, y)));
    
    let k = 0;
    for (let i = 0; i < n - k; i++) {
        for (let j = k; i >= k && j < n - k; j++) {
            for (let l = 0; l < n / 2; l++) {
                if (i < l || j < l || i + l >= n || j + l >= n) break;
                if (set.has(hash(i, j + l)) || set.has(hash(i, j - l)) || set.has(hash(i + l, j)) || set.has(hash(i - l, j))) break;
                k = Math.max(k, l + 1);
            }
        }
    }

    return k;
}

4、复杂度​

  • 时间复杂度：O(n3)O(n^3)
  • 空间复杂度：O(m)O(m)，m=mines.lengthm=mines.length

5、执行结果​

image.png