在一个 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 。
补补补！
- 思路：对于每个中心点坐标 (i,j)分别从上下左右四个方向计算以 (i,j)末尾的最长连续 1的个数，那么以(i,j)为中心的最大加号的标志为其最小值
- 创建grid矩阵和dp时，为了防止越界，因此上下左右都扩展边界
- 动态规划实现
1.确定dp数组（dp table）以及下标的含义
dp[i][j][k]:f方向为k的以 (i,j)末尾的最长连续 1的个数
2.确定递推公式
。grid[i][j]=0,dp[i][j][k]=0
。grid[i][j]=1
- k=0，向下：dp[i][j][k]=dp[i][j-1][k]+1
- k=1，向上：dp[i][j][k]=dp[i][j+1][k]+1
- k=2，向右：dp[i][j][k]=dp[i-1][j][k]+1
- k=3，向左：dp[i][j][k]=dp[i+1][j][k]+1
3.dp数组如何初始化
dp[i][j][k]=false;
4.确定遍历顺序
。k=0，上：正序j
。k=1，下：逆序j
。k=2，左：正序i
。k=3，右：逆序i
- 代码
class Solution { public int orderOfLargestPlusSign(int n, int[][] mines) { int[][] grid = new int[n + 2][n + 2]; int[][][] dp = new int[n + 2][n + 2][4]; // 初始化grid for (int i = 1; i <= n; i++){ Arrays.fill(grid[i],1); } for (int[] mine : mines){ grid[mine[0]+1][mine[1]+1] = 0; } // 更新dp for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ if (grid[i][j] == 1){ dp[i][j][0] = dp[i][j-1][0] + 1; dp[i][j][2] = dp[i-1][j][2] + 1; } } } for (int i = n; i >= 0; i--){ for (int j = n; j >= 0; j--){ if (grid[i][j] == 1){ dp[i][j][1] = dp[i][j+1][1] + 1; dp[i][j][3] = dp[i+1][j][3] + 1; } } } int res = 0; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ res = Math.max(res,Math.min(Math.min(dp[i][j][0],dp[i][j][1]),Math.min(dp[i][j][2],dp[i][j][3]))); } } return res; } }
- 复杂度
。时间复杂度：O ( n 2 )
。空间复杂度：O ( n 2 )
