首页 > 其他分享 >764. 最大加号标志

764. 最大加号标志

时间:2022-11-10 00:14:15浏览次数:72  
标签:标志 int 764 else ++ 加号 510 new Math

764. 最大加号标志

题解:

  1. 枚举二维数组每个位置,向上、下、左、右四个方向能延伸的最长长度
  2. 取这四个方向的最小值,即为答案
  3. 可以用f[i] = f[i - 1] + 1 计算四个方向的最大值,然后参考滚动数组思想,用一个变量记录即可
class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] f = new int[510][];
        boolean[][] g = new boolean[510][];
        for (int i = 0; i < n; i++) {
            g[i] = new boolean[510];
            for (int j = 0; j < n; j++) {
                g[i][j] = true;
            }
        }
        for (int[] mine : mines) {
            g[mine[0]][mine[1]] = false;
        }
        for (int i = 0; i < n; i++) {
            f[i] = new int[510];
            int s = 0;
            for (int j = 0; j < n; j++) {
                if (g[i][j]) s++;
                else s = 0;
                f[i][j] = s;
            }
        }
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (g[i][j]) s++;
                else s = 0;
                f[i][j] = Math.min(f[i][j], s);
            }
        }
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = 0; j < n; j++) {
                if (g[j][i]) s++;
                else s = 0;
                f[j][i] = Math.min(f[j][i], s);
            }
        }
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (g[j][i]) s++;
                else s = 0;
                f[j][i] = Math.min(f[j][i], s);
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                res = Math.max(res, f[i][j]);
        return res;
    }

}

标签:标志,int,764,else,++,加号,510,new,Math
From: https://www.cnblogs.com/eiffelzero/p/16875666.html

相关文章