题目形容
这是 LeetCode 上的 764. 最大加号标记 ，难度为 中等。
Tag :「模仿」、「预处理」
在一个 $n \times n$ 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其余每个元素都为 1。$mines[i] = [x_i, y_i]$ 示意 $grid[x_i][y_i] = 0$。
返回 grid 中蕴含 1 的最大的 轴对齐 加号标记的阶数。如果未找到加号标记，则返回 0。
一个 k 阶由 1 组成的“轴对称”加号标记 具备核心网格 $grid[r] = 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 <= x_i, y_i < n$
- 每一对 $(x_i, y_i)$ 都 不反复
预处理 + 模仿
假如点 $(x, y)$ 可能获得最大长度 $k$，咱们晓得 $k$ 取决于以点 $(x, y)$ 为终点，四联通方向中「最短的间断 $1$ 的长度」。
基于此，咱们能够建设四个大小为 $n \times n$ 的矩阵（二维数组）a、b、c 和 d 别离代表四个方向间断 $1$ 的前缀数：
数据范畴为 $500$，预处理前缀数组复杂度为 $O(n^2)$，统计答案复杂度为 $O(n^2)$，工夫复杂度没有问题。
再思考空间，建设四个方向的前缀数组所需空间为 $500 \times 500 \times 4 = 10^6$，即便加上原矩阵 g 也不会有 MLE 危险，空间复杂度也没有问题。
Java 代码：
class Solution {public int orderOfLargestPlusSign(int n, int[][] mines) {int[][] g = new int[n + 10][n + 10];
for (int i = 1; i <= n; i++) Arrays.fill(g[i], 1);
for (int[] info : mines) g[info[0] + 1][info[1] + 1] = 0;
int[][] a = new int[n + 10][n + 10], b = new int[n + 10][n + 10], c = new int[n + 10][n + 10], d = new int[n + 10][n + 10];
for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (g[i][j] == 1) {a[i][j] = a[i - 1][j] + 1;
b[i][j] = b[i][j - 1] + 1;
}
if (g[n + 1 - i][n + 1 - j] == 1) {c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1;
d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {ans = Math.max(ans, Math.min(Math.min(a[i][j], b[i][j]), Math.min(c[i][j], d[i][j])));
}
}
return ans;
}
}TypeScript 代码：
function orderOfLargestPlusSign(n: number, mines: number[][]): number {function getMat(x: number, y: number, val: number): number[][] {const ans = new Array<Array<number>>(x)
for (let i = 0; i < x; i++) ans[i] = new Array<number>(y).fill(val)
return ans
}
const g = getMat(n + 10, n + 10, 1)
for (const info of mines) g[info[0] + 1][info[1] + 1] = 0
const a = getMat(n + 10, n + 10, 0), b = getMat(n + 10, n + 10, 0), c = getMat(n + 10, n + 10, 0), d = getMat(n + 10, n + 10, 0)
for (let i = 1; i <= n; i++) {for (let j = 1; j <= n; j++) {if (g[i][j] == 1) {a[i][j] = a[i - 1][j] + 1
b[i][j] = b[i][j - 1] + 1
}
if (g[n + 1 - i][n + 1 - j] == 1) {c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1
d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1
}
}
}
let ans = 0
for (let i = 1; i <= n; i++) {for (let j = 1; j <= n; j++) {ans = Math.max(ans, Math.min(Math.min(a[i][j], b[i][j]), Math.min(c[i][j], d[i][j])))
}
}
return ans
}Python 代码：
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
g = [[1] * (n + 10) for _ in range(n + 10)]
for x, y in mines:
g[x + 1][y + 1] = 0
a, b, c, d = [[0] * (n + 10) for _ in range(n + 10)], [[0] * (n + 10) for _ in range(n + 10)], [[0] * (n + 10) for _ in range(n + 10)], [[0] * (n + 10) for _ in range(n + 10)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if g[i][j] == 1:
a[i][j] = a[i - 1][j] + 1
b[i][j] = b[i][j - 1] + 1
if g[n + 1 - i][n + 1 - j] == 1:
c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1
d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1
ans = 0
for i in range(1, n + 1):
for j in range(1, n + 1):
ans = max(ans, min(min(a[i][j], b[i][j]), min(c[i][j], d[i][j])))
return ans- 工夫复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.764 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
本文由 mdnice 多平台公布