给定一个二维的 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 的正方形。