Medium

题目描述

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大正方形子网格，并返回该正方形的面积。如果不存在，则返回 0。

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

提示：

  • 1 <= grid.length <= 100
  • 1 <= grid[0].length <= 100
  • grid[i][j] 为 0 或 1

解题思路

这道题需要找到边界全部为 1 的最大正方形。核心思路是使用动态规划预处理每个位置的连续 1 信息。

解题思路：

  1. 预处理阶段：对每个位置 (i,j)，计算从该位置向左和向上连续 1 的长度。使用两个 DP 数组：

    • left[i][j]：从位置 (i,j) 向左连续 1 的个数（包括自己）
    • up[i][j]：从位置 (i,j) 向上连续 1 的个数（包括自己）

  2. 枚举正方形：以每个位置为右下角，枚举所有可能的正方形边长。对于边长为 len 的正方形，需要检查：

    • 右下角 (i,j) 向左至少有 len 个连续的 1
    • 右下角 (i,j) 向上至少有 len 个连续的 1
    • 左下角 (i, j-len+1) 向上至少有 len 个连续的 1
    • 右上角 (i-len+1, j) 向左至少有 len 个连续的 1

  3. 优化策略：从大到小枚举边长，一旦找到合法正方形就可以直接返回，因为我们要找最大面积。

时间复杂度为 O(n³)，空间复杂度为 O(n²)。这是一个经典的二维DP + 枚举优化问题。

代码实现

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> left(m, vector<int>(n, 0));
        vector<vector<int>> up(m, vector<int>(n, 0));
        
        // 预处理每个位置向左和向上连续1的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    left[i][j] = j == 0 ? 1 : left[i][j-1] + 1;
                    up[i][j] = i == 0 ? 1 : up[i-1][j] + 1;
                }
            }
        }
        
        int maxLen = 0;
        // 枚举每个位置作为正方形右下角
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从可能的最大边长开始枚举
                int maxPossible = min(left[i][j], up[i][j]);
                for (int len = maxPossible; len >= 1; len--) {
                    // 检查能否构成边长为len的正方形
                    if (up[i][j-len+1] >= len && left[i-len+1][j] >= len) {
                        maxLen = max(maxLen, len);
                        break; // 找到最大的就可以break了
                    }
                }
            }
        }
        
        return maxLen * maxLen;
    }
};

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        left = [[0] * n for _ in range(m)]
        up = [[0] * n for _ in range(m)]
        
        # 预处理每个位置向左和向上连续1的个数
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    left[i][j] = 1 if j == 0 else left[i][j-1] + 1
                    up[i][j] = 1 if i == 0 else up[i-1][j] + 1
        
        max_len = 0
        # 枚举每个位置作为正方形右下角
        for i in range(m):
            for j in range(n):
                # 从可能的最大边长开始枚举
                max_possible = min(left[i][j], up[i][j])
                for length in range(max_possible, 0, -1):
                    # 检查能否构成边长为length的正方形
                    if up[i][j-length+1] >= length and left[i-length+1][j] >= length:
                        max_len = max(max_len, length)
                        break  # 找到最大的就可以break了
        
        return max_len * max_len

public class Solution {
    public int Largest1BorderedSquare(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[,] left = new int[m, n];
        int[,] up = new int[m, n];
        
        // 预处理每个位置向左和向上连续1的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    left[i, j] = j == 0 ? 1 : left[i, j-1] + 1;
                    up[i, j] = i == 0 ? 1 : up[i-1, j] + 1;
                }
            }
        }
        
        int maxLen = 0;
        // 枚举每个位置作为正方形右下角
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从可能的最大边长开始枚举
                int maxPossible = Math.Min(left[i, j], up[i, j]);
                for (int len = maxPossible; len >= 1; len--) {
                    // 检查能否构成边长为len的正方形
                    if (up[i, j-len+1] >= len && left[i-len+1, j] >= len) {
                        maxLen = Math.Max(maxLen, len);
                        break; // 找到最大的就可以break了
                    }
                }
            }
        }
        
        return maxLen * maxLen;
    }
}

var largest1BorderedSquare = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Precompute horizontal and vertical consecutive 1s
    const horizontal = Array(m).fill().map(() => Array(n).fill(0));
    const vertical = Array(m).fill().map(() => Array(n).fill(0));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                horizontal[i][j] = j === 0 ? 1 : horizontal[i][j-1] + 1;
                vertical[i][j] = i === 0 ? 1 : vertical[i-1][j] + 1;
            }
        }
    }
    
    let maxArea = 0;
    
    // Try all possible top-left corners
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                // Try all possible square sizes starting from this corner
                const maxPossibleSize = Math.min(m - i, n - j);
                for (let size = 1; size <= maxPossibleSize; size++) {
                    const bottomRow = i + size - 1;
                    const rightCol = j + size - 1;
                    
                    // Check if we can form a square of this size
                    if (horizontal[i][rightCol] >= size && // top border
                        horizontal[bottomRow][rightCol] >= size && // bottom border
                        vertical[bottomRow][j] >= size && // left border
                        vertical[bottomRow][rightCol] >= size) { // right border
                        maxArea = Math.max(maxArea, size * size);
                    }
                }
            }
        }
    }
    
    return maxArea;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n×min(m,n))预处理需要O(m×n)，枚举正方形需要O(m×n×min(m,n))
空间复杂度O(m×n)需要两个二维数组存储left和up信息