leetcode764 最大加号标志

题目

在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

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

例子
输入输出示例
输入输出示例

分析

使用一个down数组和一个right数组分别存从上到下的连续1个个数，和从左到右的连续1的个数。从最开始的1阶加号开始找，找到了就找2阶加号，依次类推。到(i,j)位置的时候就利用刚刚存好的right数组和down数组判断以当前位置为加号最下端，是否能构成n阶加号。所以整个过程只需要时间复杂度:O(NN),空间复杂度O(NN)。

代码

class Solution {
public:
    int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {

        //初始化矩阵
        vector<vector<int>> nums(N, vector<int>(N, 1));
        for (auto v : mines){
            nums[v[0]][v[1]] = 0;
        }

        vector<vector<int>> right(N, vector<int>(N, 0));
        vector<vector<int>> down(N, vector<int>(N, 0));

        int find = 1;

        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (j == 0){
                    right[i][j] = nums[i][j];
                }else if (nums[i][j] == 1){
                    right[i][j] = right[i][j - 1] + 1;
                }

                if (i == 0){
                    down[i][j] = nums[i][j];
                }else if (nums[i][j] == 1){
                    down[i][j] = down[i - 1][j] + 1;
                }

                if (nums[i][j] == 1 && is_plus(right, down, i, j, find - 1)){
                    find++;
                }
            }
        }

        return find - 1;
    }

    bool is_plus(vector<vector<int>> &right, vector<vector<int>> &down, int i, int j, int n){

        if (n == 0 && (down[i][j] == 1 || right[i][j] == 1)){
            return true;
        }

        //边界条件
        if (i - n < 0 || i - 2 * n < 0 || j - n < 0 || j + n >= right[0].size()){
            return false;
        }

        //有0
        if (down[i - n][j] == 0 || down[i - 2 * n][j] == 0 || right[i - n][j] == 0 || right[i - n][j - n] == 0 || right[i - n][j + n] == 0){
            return false;
        }

        //满足条件
        if (down[i][j] - down[i - n][j] == n && down[i - n][j] - down[i - 2 * n][j] == n && 
            right[i - n][j] - right[i - n][j - n] == n && right[i - n][j + n] - right[i - n][j] == n){
            return true;
        }

        return false;
    }
};