764. 最大加号标志

Medium

题目描述

给你一个整数 n。你有一个大小为 n x n 的二进制网格 grid，最初所有值都是 1，除了 mines 数组中给出的一些索引位置。mines 数组的第 i 个元素定义为 mines[i] = [xi, yi]，其中 grid[xi][yi] == 0。

返回 grid 中包含的最大轴对齐加号标志的阶数。如果不存在，则返回 0。

阶数为 k 的轴对齐加号标志以某个中心 grid[r][c] == 1 为基础，同时向上、下、左、右四个方向延伸长度为 k - 1 的臂，且这些臂都由 1 组成。注意，加号标志的臂之外可能有 0 或 1，只有加号标志的相关区域需要检查是否为 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) 都是唯一的。

解题思路

这道题要求找到网格中最大的加号标志。核心思路是对每个位置计算其四个方向上连续1的个数，然后取最小值作为该位置能形成的加号标志的阶数。

解题思路：

预处理网格：根据mines数组构建实际的网格，标记哪些位置是0。
动态规划计算四个方向：
- 对于每个位置 (i,j)，计算四个方向上连续1的个数
- left[i][j]：从当前位置向左连续1的个数
- right[i][j]：从当前位置向右连续1的个数
- up[i][j]：从当前位置向上连续1的个数
- down[i][j]：从当前位置向下连续1的个数
计算每个位置的加号阶数：位置 (i,j) 能形成的最大加号阶数为 min(left[i][j], right[i][j], up[i][j], down[i][j])
优化空间：可以用一个数组存储四个方向的最小值，边计算边更新。

算法流程：

初始化所有位置的连续1个数为网格大小
将mines位置标记为0
四次遍历网格，分别计算四个方向的连续1个数，并实时更新每个位置的最小值
返回所有位置中的最大值

时间复杂度O(n²)，空间复杂度O(n²)，是一个高效的动态规划解法。

代码实现

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> dp(n, vector<int>(n, n));
        unordered_set<int> banned;
        for (auto& mine : mines) {
            banned.insert(mine[0] * n + mine[1]);
        }
        
        int result = 0;
        
        for (int r = 0; r < n; r++) {
            int count = 0;
            // 从左到右
            for (int c = 0; c < n; c++) {
                count = banned.count(r * n + c) ? 0 : count + 1;
                dp[r][c] = min(dp[r][c], count);
            }
            
            count = 0;
            // 从右到左
            for (int c = n - 1; c >= 0; c--) {
                count = banned.count(r * n + c) ? 0 : count + 1;
                dp[r][c] = min(dp[r][c], count);
            }
        }
        
        for (int c = 0; c < n; c++) {
            int count = 0;
            // 从上到下
            for (int r = 0; r < n; r++) {
                count = banned.count(r * n + c) ? 0 : count + 1;
                dp[r][c] = min(dp[r][c], count);
            }
            
            count = 0;
            // 从下到上
            for (int r = n - 1; r >= 0; r--) {
                count = banned.count(r * n + c) ? 0 : count + 1;
                dp[r][c] = min(dp[r][c], count);
                result = max(result, dp[r][c]);
            }
        }
        
        return result;
    }
};

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        dp = [[n] * n for _ in range(n)]
        banned = {r * n + c for r, c in mines}
        
        result = 0
        
        for r in range(n):
            count = 0
            # 从左到右
            for c in range(n):
                count = 0 if r * n + c in banned else count + 1
                dp[r][c] = min(dp[r][c], count)
            
            count = 0
            # 从右到左
            for c in range(n - 1, -1, -1):
                count = 0 if r * n + c in banned else count + 1
                dp[r][c] = min(dp[r][c], count)
        
        for c in range(n):
            count = 0
            # 从上到下
            for r in range(n):
                count = 0 if r * n + c in banned else count + 1
                dp[r][c] = min(dp[r][c], count)
            
            count = 0
            # 从下到上
            for r in range(n - 1, -1, -1):
                count = 0 if r * n + c in banned else count + 1
                dp[r][c] = min(dp[r][c], count)
                result = max(result, dp[r][c])
        
        return result

public class Solution {
    public int OrderOfLargestPlusSign(int n, int[][] mines) {
        int[,] dp = new int[n, n];
        HashSet<int> banned = new HashSet<int>();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = n;
            }
        }
        
        foreach (var mine in mines) {
            banned.Add(mine[0] * n + mine[1]);
        }
        
        int result = 0;
        
        for (int r = 0; r < n; r++) {
            int count = 0;
            // 从左到右
            for (int c = 0; c < n; c++) {
                count = banned.Contains(r * n + c) ? 0 : count + 1;
                dp[r, c] = Math.Min(dp[r, c], count);
            }
            
            count = 0;
            // 从右到左
            for (int c = n - 1; c >= 0; c--) {
                count = banned.Contains(r * n + c) ? 0 : count + 1;
                dp[r, c] = Math.Min(dp[r, c], count);
            }
        }
        
        for (int c = 0; c < n; c++) {
            int count = 0;
            // 从上到下
            for (int r = 0; r < n; r++) {
                count = banned.Contains(r * n + c) ? 0 : count + 1;
                dp[r, c] = Math.Min(dp[r, c], count);
            }
            
            count = 0;
            // 从下到上
            for (int r = n - 1; r >= 0; r--) {
                count = banned.Contains(r * n + c) ? 0 : count + 1;
                dp[r, c] = Math.Min(dp[r, c], count);
                result = Math.Max(result, dp[r, c]);
            }
        }
        
        return result;
    }
}

var orderOfLargestPlusSign = function(n, mines) {
    const dp = Array(n).fill().map(() => Array(n).fill(n));
    const banned = new Set();
    
    for (const mine of mines) {
        banned.add(mine[0] * n + mine[1]);
    }
    
    let result = 0;
    
    for (let r = 0; r < n; r++) {
        let count = 0;
        // 从左到右
        for (let c = 0; c < n; c++) {
            count = banned.has(r * n + c) ? 0 : count + 1;
            dp[r][c] = Math.min(dp[r][c], count);
        }
        
        count = 0;
        // 从右到左
        for (let c = n - 1; c >= 0; c--) {
            count = banned.has(r * n + c) ? 0 : count + 1;
            dp[r][c] = Math.min(dp[r][c], count);
        }
    }
    
    for (let c = 0; c < n; c++) {
        let count = 0;
        // 从上到下
        for (let r = 0; r < n; r++) {
            count = banned.has(r * n + c) ? 0 : count + 1;
            dp[r][c] = Math.min(dp[r][c], count);
        }
        
        count = 0;
        // 从下到上
        for (let r = n - 1; r >= 0; r--) {
            count = banned.has(r * n + c) ? 0 : count + 1;
            dp[r][c] = Math.min(dp[r][c], count);
            result = Math.max(result, dp[r][c]);
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n²)	需要遍历整个网格4次，每次O(n²)
空间复杂度	O(n²)	需要dp数组存储每个位置的结果，以及banned集合存储地雷位置

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目