Leetcode 764. 最大加号标志

Posted on In ,

题目描述

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

解答

  • 一开始想用侵蚀法写一下，离空洞最远的点的距离可能就是答案。 后来仔细一想，那样的话是求一个曼哈顿距离的最大圆半径，和找十字还是不一样。 找十字就只要在二维上找最大长度就好了。 另外侵蚀的复杂度：\(O(n^3)\) n为边长 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    class Solution {
    public:
        int map[500][500]={0};
        int lens[500][500][4]={0};
        int len;
        int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
            for (int i=0;i<mines.size();i++){
                map[mines[i][0]][mines[i][1]]=1;
            }
            //left 2 right
            for (int i=0;i<n;i++){
                len=0;
                for (int j=0;j<n;j++){
                    if (map[i][j]==1){
                        len=0;
                    }
                    else{
                        len++;
                        lens[i][j][0]=len;
                    }
                }
            }
            //right to left
            for (int i=0;i<n;i++){
                len=0;
                for (int j=n-1;j>=0;j--){
                    if (map[i][j]==1){
                        len=0;
                    }
                    else{
                        len++;
                        lens[i][j][1]=len;
                    }
                }
            }
            //up to down
            for (int i=0;i<n;i++){
                len=0;
                for (int j=0;j<n;j++){
                    if (map[j][i]==1){
                        len=0;
                    }
                    else{
                        len++;
                        lens[j][i][2]=len;
                    }
                }
            }
            //down to up
            for (int i=0;i<n;i++){
                len=0;
                for (int j=n-1;j>=0;j--){
                    if (map[j][i]==1){
                        len=0;
                    }
                    else{
                        len++;
                        lens[j][i][3]=len;
                    }
                }
            }
            int ans=0;
            for (int i=0;i<n;i++)
                for (int j=0;j<n;j++){
                    ans=max(ans,min({lens[i][j][3],lens[i][j][2],lens[i][j][1],lens[i][j][0]}));
                }
            return ans;
        }
    };
    ### Complexity

  • Time: \(O(n^2)\)

  • Space: \(O(n^2)\) ## 题外话

  • 写leetcode题目还是不要用复杂的动态数据了，一次性开个大一点的2D array就好了。 本来是想动态写一个，后来觉得申明和删除都要for，太麻烦了。 以后还是写python水水好了。