Skip to main content

1139. 最大的以 1 为边界的正方形[medium]

1139. 最大的以 1 为边界的正方形[medium]​

https://leetcode-cn.com/problems/largest-1-bordered-square

给你一个由若干 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

通过次数2,967 提交次数6,773

Second Try​

2020-06-09

感觉这道题还是挺难的，要是没把握到解题的诀窍很难处理好。

这个思路的解法不错，按图形扫描下来比较容易理解。但是就算看了题解知道了思路，复写的时候还是花了半个钟头的时间，wtf.

  • 沿着i,j的坐标，从左到右，从上到下，一行行扫描下来
  • 保存每个坐标在左方向和上方向的连续“1”数量，使用两个矩阵数列进行保存。这两个方向分别代表着正方形的下边和右边两条边，矩阵也保留着可能的长度。
  • 每次扫描到1，则矩阵数值取前值加1，否则保持默认值0。如果前值为0，则遇到下一个1的时候又从头算起。
  • 扫描到1的时候，查看当前最长的正方形矩阵，本质上是在四个方向的边中选择最短的那条。目前有两条可能确定的边，其最短值为k。需要检查左边和上边两条边的连续1的数量，恰巧也可以通过缓存矩阵直接读取。因此可以从1开始遍历到k的长度，最长正方形就在1到k之间。
  • 不停比较，遍历完就得到最长的边maxl, 返回maxl * maxl.
  • 缓存矩阵的存在，使这道题变成了动态规划的题目。
class Solution(object):
    def largest1BorderedSquare(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        left_count = [[0 for i in range(n)] for j in range(m)]
        # up_count = left_count + [] # bug
        up_count = [[i for i in inner] for inner in left_count] # copy
        maxl = 0
        for i in range(0, m):
            for j in range(0, n):
                if grid[i][j] == 0:
                    continue
                left_count[i][j] = up_count[i][j] = 1
                if i > 0:
                    up_count[i][j] = up_count[i-1][j] + 1
                if j > 0:
                    left_count[i][j] = left_count[i][j-1] + 1
                longest_match = min(left_count[i][j], up_count[i][j])
                for k in range(1, longest_match + 1):
                    if up_count[i][j - k + 1] >= k and left_count[i - k + 1][j] >= k:
                        maxl = max(maxl, k)
        return maxl * maxl
  • 执行用时 :172 ms, 在所有 Python 提交中击败了65.22%的用户
  • 内存消耗 :13 MB, 在所有 Python 提交中击败了100.00%的用户

First Try​

first try想要使用遍历法，失败了，一堆bug还进行不下去。