LeetCode1139-最大的以1为边界的正方形

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/largest-1-bordered-square/

中文链接：https://leetcode-cn.com/problems/largest-1-bordered-square/

题目详述

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

示例 1：

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

示例 2：

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

提示：

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

题目详解

  • 枚举每一个正方形。
  • 第一层循环枚举正方形的长度 len，第二三层循环正方形的左上角。
  • 对于每个正方形，我们需要尽可能快地判断它是否满足条件，这就需要进行预处理。通过预处理，得到每个点向下有多少个连续的 1、向右有多少个连续的 1。通过左上角可以得到其他三个点，再结合预处理后的结果，可以在常数时间内判断此正方形是否满足条件。
  • 时间复杂度为 O(m * n * min(m, n))。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LeetCode_01139 {

    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] down = new int[m][n];
        int[][] right = new int[m][n];
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    down[i][j] += i + 1 < m ? down[i + 1][j] + 1 : 1;
                    right[i][j] += j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int len = Math.min(m, n); len > 0; --len) {
            for (int i = 0; i <= m - len; ++i) {
                for (int j = 0; j <= n - len; ++j) {
                    if (down[i][j] >= len && right[i][j] >= len && right[i + len - 1][j] >= len && down[i][j + len - 1] >= len) {
                        return len * len;
                    }
                }
            }
        }
        return 0;
    }
}