宫水三叶的刷题日记

V1

2022/11/09阅读:10主题:全栈蓝

764. 最大加号标志 : 常规「预处理 + 模拟」运用题

题目描述

这是 LeetCode 上的 764. 最大加号标志 ,难度为 中等

Tag : 「模拟」、「预处理」

在一个 的矩阵 grid 中,除了在数组 mines 中给出的元素为 0,其他每个元素都为 1 表示 

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

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

示例 1:

输入: n = 5, mines = [[4, 2]]

输出: 2

解释: 在上面的网格中,最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2:

输入: n = 1, mines = [[0, 0]]

输出: 0

解释: 没有加号标志,返回 0 。

提示:

  • 每一对   都 不重复

预处理 + 模拟

假设点 能够取得最大长度 ,我们知道 取决于以点 为起点,四联通方向中「最短的连续 的长度」。

基于此,我们可以建立四个大小为 的矩阵(二维数组)abcd 分别代表四个方向连续 的前缀数:

image.png
image.png

数据范围为 ,预处理前缀数组复杂度为 ,统计答案复杂度为 ,时间复杂度没有问题。

再考虑空间,建立四个方向的前缀数组所需空间为 ,即使加上原矩阵 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 + 101)
    for (const info of mines) g[info[0] + 1][info[1] + 1] = 0
    const a = getMat(n + 10, n + 100), b = getMat(n + 10, n + 100), c = getMat(n + 10, n + 100), d = getMat(n + 10, n + 100)
    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 + 10for _ in range(n + 10)]
        for x, y in mines:
            g[x + 1][y + 1] = 0
        a, b, c, d = [[0] * (n + 10for _ in range(n + 10)], [[0] * (n + 10for _ in range(n + 10)], [[0] * (n + 10for _ in range(n + 10)], [[0] * (n + 10for _ 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
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.764 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1