欢迎24级新生

2227. Maximal Square (Medium)

给定一个二维的 0-1 矩阵,求全由 1 构成的最大正方形面积。

输入

输入是一个二维 0-1 数组

输出

输出是最大正方形面积。

样例

标准输入 复制文本
[["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
标准输出 复制文本
4

提示

对于在矩阵内搜索正方形或长方形的题型,一种常见的做法是定义一个二维 dp 数组,其中dp[i][j] 表示满足题目条件的、以 (i, j) 为右下角的正方形或者长方形的属性。对于本题,则表示以 (i, j) 为右下角的全由 1 构成的最大正方形面积。如果当前位置是 0,那么 dp[i][j] 即为 0;如果当前位置是 1,我们假设 dp[i][j] = k2,其充分条件为 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 的值必须都不小于 (k − 1)2,否则 (i, j) 位置不可以构成一个边长为 k 的正方形。同理,如果这三个值中的的最小值为 k − 1,则 (i, j) 位置一定且最大可以构成一个边长为 k 的正方形。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 0
通过 0