LeetCode 1139. 最大的以 1 为边界的正方形

Categories:

题目描述
思路分析
1. 解法一：前缀方向 DP（推荐）
相似题目

题目描述

✅ 1139. 最大的以 1 为边界的正方形

思路分析

解法一：前缀方向 DP（推荐）

核心思路：

预处理 hor[i][j] 与 ver[i][j]，分别表示向左/向上连续 1 的数量。

枚举每个位置作为正方形右下角，尝试最大可能边长。

只需检查上边与左边是否满足长度即可。

复杂度分析：

时间复杂度：O(mn * min(m,n))，其中 m、n 为网格行列数。

空间复杂度：O(mn)，用于保存 DP 数组。

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] hor = new int[m][n];
        int[][] ver = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    hor[i][j] = (j == 0 ? 0 : hor[i][j - 1]) + 1;
                    ver[i][j] = (i == 0 ? 0 : ver[i - 1][j]) + 1;
                }
            }
        }

        int best = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int size = Math.min(hor[i][j], ver[i][j]);
                while (size > best) {
                    if (ver[i][j - size + 1] >= size && hor[i - size + 1][j] >= size) {
                        best = size;
                        break;
                    }
                    size--;
                }
            }
        }

        return best * best;
    }
}

func largest1BorderedSquare(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])

	hor := make([][]int, m)
	ver := make([][]int, m)
	for i := 0; i < m; i++ {
		hor[i] = make([]int, n)
		ver[i] = make([]int, n)
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				if j == 0 {
					hor[i][j] = 1
				} else {
					hor[i][j] = hor[i][j-1] + 1
				}
				if i == 0 {
					ver[i][j] = 1
				} else {
					ver[i][j] = ver[i-1][j] + 1
				}
			}
		}
	}

	best := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			size := hor[i][j]
			if ver[i][j] < size {
				size = ver[i][j]
			}
			for size > best {
				if ver[i][j-size+1] >= size && hor[i-size+1][j] >= size {
					best = size
					break
				}
				size--
			}
		}
	}

	return best * best
}

相似题目

题目	难度	考察点
1139. 最大的以 1 为边界的正方形	中等	DP
1277. 统计全为 1 的正方形子矩阵	中等	DP
221. 最大正方形	中等	DP
463. 岛屿的周长	简单	网格
695. 岛屿的最大面积	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/42472779