1139. Largest 1-Bordered Square¶
题目信息¶
- 题号:
1139
- 难度:
Medium
- 主题:
二进制矩阵、正方形边框、动态规划
- 原题:
- 重点:
正方形四条边必须全部为
1,内部格可以为0或1;返回最大正方形面积,不存在时返回0
题目重述¶
给定只包含 0 和 1 的矩阵 grid。寻找一个行列范围连续且边长相等的正方形子矩阵,使其顶部、底部、左侧和右侧边框上的所有格子都为 1。
正方形内部的格子没有限制。请返回满足条件的最大正方形面积;若连边长为 1 的全 1 正方形也不存在,返回 0。
1 <= grid.length, grid[i].length <= 100,每个格子为 0 或 1。
自建示例¶
左上角存在边长为二的完整边框:
输入:grid = [[1,1,0],[1,1,0],[0,0,0]]
输出:4
解释:左上角 2 x 2 子矩阵的四条边均为 1,面积为 4;不存在更大的合法正方形。
矩阵没有任何一:
输入:grid = [[0,0],[0,0]]
输出:0
解释:不存在边长为 1 的全 1 正方形,因此返回 0。